Design & Analysis of Algorithms Question Paper - June 2015 - Computer Engineering (Semester 7)

36views

written 5.8 years ago by

Design & Analysis of Algorithms - June 2015

SPPU Computer Engineering (Semester 7)

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 marks

1 (b) Solve following recurrence:
t(n)-2 t(n-1)=3ⁿ. 10 marks

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 marks

2 (b) Write an algorithm for merge sort. State its time complexity by solving recurrence equation of merge sort. 10 marks

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. 10 marks

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. 10 marks

4 (a) Explain multistage graph problem with forward approach using dynamic programming with an example. 10 marks

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

10 marks

Answer any one question from Q5 and Q6

5 (a) Explain in detail backtracking strategy and give control abstraction for the same. 10 marks

5 (b) Write the control abstraction for LC-Search. Explain how Traveling Salesperson problem is solved using LCBB. 10 marks

6 (a) Write an algorithm on Hamiltonian cycles using Backtracking Strategy. 10 marks

6 (b) Write an algorithm to solve n Queen's problem using backtracking methods. What is the time complexity of this algorithm? 10 marks

Answer any one question from Q7 and Q8

7 (a) State and explain in detail Cook's theorem. 10 marks

7 (b) Describe with example following class:
i) P ii) NP 10 marks

8 (a) Prove that CNF-SAT is polynomially transformable to DHC, hence DHC is NP-complete. 10 marks

8 (b) Explain NP hard code generation problem. 10 marks

Answer any one question from Q9 and Q10

9 (a) Explain in detail with example Logarithmic time merging algorithm. 10 marks

9 (b) Explain with example parallel evaluation of expression. 10 marks

10 (a) Explain All pairs shortest paths. Also give parallel shortest paths algorithm. 10 marks

10 (b) State and explain pointer doubling problem with algorithm, what is the time complexity of this algorithm. 10 marks

Answer any one question from Q11 and Q12

11 (a) Explain Resource - Allocation algorithm with deadlock avoidance. 10 marks

11 (b) Explain in detail sorting and convex Hull algorithm. 10 marks

12 (a) Explain Image edge detection algorithm. 10 marks

12 (b) Explain how Huffman's technique is used for data coding. 10 marks

ADD COMMENT EDIT