STUPIDSID
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.
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.
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
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