Analysis of Algorithms - Dec 2015
Computer Engineering (Semester 4)
TOTAL MARKS: 80
TOTAL TIME: 3 HOURS(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks.1 (a) Define 0, Ω, and θ notations. To find the complexity of given recurrence relation.
i) T(n)=4T(n/2)+n3
ii) T(n)=2T (n/2)+n3.(10 marks)1 (b) Implement the binary search, and derive its complexity.(10 marks)2 (a) Explain 0/1 knapsack problem using dynamic programming.(10 marks)2 (b) Explain optimal storage on tapes and find the optimal order for given instance.
n=3, and (11, 12, 13)=(5, 10, 3).(10 marks)3 (a) Let n=4, (p1, p2, p3, p4)=(100, 10, 15, 27) and (d1, d2, d3, d4) = (2, 1, 2, 1). Find feasible solutions, using job sequencing with deadlines.(10 marks)3 (b) Find a minimum cost path from 3 to 3 in the given graph using dynamic programming.
(10 marks)4 (a) Explain 8 Queen problem.(10 marks)4 (b) Explain sum of subset problem. Find all possible subsets of weight that sum to m, let n=6, m=30, and w[1:6]={5, 10, 12, 13, 15, 18}(10 marks)5 (a) Write an algorithm for Kunth-Morrie-Pratt (KMP).(10 marks)5 (b) Explain the Strassen's Matrix multiplication.(10 marks)
TOTAL TIME: 3 HOURS(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks.1 (a) Define 0, Ω, and θ notations. To find the complexity of given recurrence relation.
i) T(n)=4T(n/2)+n3
ii) T(n)=2T (n/2)+n3.(10 marks)1 (b) Implement the binary search, and derive its complexity.(10 marks)2 (a) Explain 0/1 knapsack problem using dynamic programming.(10 marks)2 (b) Explain optimal storage on tapes and find the optimal order for given instance.
n=3, and (11, 12, 13)=(5, 10, 3).(10 marks)3 (a) Let n=4, (p1, p2, p3, p4)=(100, 10, 15, 27) and (d1, d2, d3, d4) = (2, 1, 2, 1). Find feasible solutions, using job sequencing with deadlines.(10 marks)3 (b) Find a minimum cost path from 3 to 3 in the given graph using dynamic programming.
(10 marks)4 (a) Explain 8 Queen problem.(10 marks)4 (b) Explain sum of subset problem. Find all possible subsets of weight that sum to m, let n=6, m=30, and w[1:6]={5, 10, 12, 13, 15, 18}(10 marks)5 (a) Write an algorithm for Kunth-Morrie-Pratt (KMP).(10 marks)5 (b) Explain the Strassen's Matrix multiplication.(10 marks)Write note on (any two):
6 (a) Randomized Algorithms.(10 marks)6 (b) Branch and bound strategy(10 marks)6 (c) Huffman coding.(10 marks)6 (d) Rabin karp algorithm(10 marks)
