MORE IN Design & Analysis of Algorithms
SPPU Computer Engineering (Semester 7)
Design & Analysis of Algorithms
June 2015
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

Answer any one question from Q1 and Q2
1 (a) Give Greedy Prim's minimum spanning tree algorithm. Also explain it with suitable example.
10 M
1 (b) Solve following recurrence:
t(n)-2 t(n-1)=3n.
8 M

2 (a) Write an algorithm for Knapsack greedy problem. Find an optimal solution for following knapsack problem: n=4, M=70, w= {10, 20, 30, 40}, P = {20, 30, 40, 50}
10 M
2 (b) Write an algorithm for merge sort. State its time complexity by solving recurrence equation of merge sort.
8 M

Answer any one question from Q3 and Q4
3 (a) Let n = 4 and {k1, k2, k3, k4} = {do, if, int, while}.
Let p(1:4) = {3, 3, 1, 1}
Let q(0:4) = {2, 3, 1, 1, 1}
Compute & construct OBST for above values.
8 M
3 (b) State and explain the principle of dynamic programming. Name the elements of dynamic programming and give the difference between dynamic programming and Greedy method.
8 M

4 (a) Explain multistage graph problem with forward approach using dynamic programming with an example.
8 M
4 (b) Define the Travelling Salesperson Problem. Solve the TSP problem using Dynamic programming where the edge lengths are given as:
 0 10 15 20 5 0 9 10 6 13 0 12 8 8 9 0
8 M

Answer any one question from Q5 and Q6
5 (a) Explain in detail backtracking strategy and give control abstraction for the same.
8 M
5 (b) Write the control abstraction for LC-Search. Explain how Traveling Salesperson problem is solved using LCBB.
8 M

6 (a) Write an algorithm on Hamiltonian cycles using Backtracking Strategy.
8 M
6 (b) Write an algorithm to solve n Queen's problem using backtracking methods. What is the time complexity of this algorithm?
8 M

Answer any one question from Q7 and Q8
7 (a) State and explain in detail Cook's theorem.
10 M
7 (b) Describe with example following class:
i) P ii) NP
8 M

8 (a) Prove that CNF-SAT is polynomially transformable to DHC, hence DHC is NP-complete.
10 M
8 (b) Explain NP hard code generation problem.
8 M

Answer any one question from Q9 and Q10
9 (a) Explain in detail with example Logarithmic time merging algorithm.
8 M
9 (b) Explain with example parallel evaluation of expression.
8 M

10 (a) Explain All pairs shortest paths. Also give parallel shortest paths algorithm.
8 M
10 (b) State and explain pointer doubling problem with algorithm, what is the time complexity of this algorithm.
8 M

Answer any one question from Q11 and Q12
11 (a) Explain Resource - Allocation algorithm with deadlock avoidance.
8 M
11 (b) Explain in detail sorting and convex Hull algorithm.
8 M

12 (a) Explain Image edge detection algorithm.
8 M
12 (b) Explain how Huffman's technique is used for data coding.
8 M

More question papers from Design & Analysis of Algorithms