STUPIDSID
Answer any one question from Q1 and Q2
1 (a)
Write the recurrence relation for binary search and solve it.
6 M
1 (b)
Explain the Greedy Prim's minimum spanning tree algorithm.
4 M
1 (c)
Write control abstraction for divide and conquer algorithmic strategy. Also write recurrence relation for the same.
5 M
1 (d)
Define asymptotic notations. Explain their significance in analyzing algorithms.
3 M
2 (a)
Write an algorithm for quick sort. State its time complexity.
6 M
2 (b)
Solve the following instance of 'job sequencing with deadlines' problem: n = 7, profits (p1, p2, p3, ........,p7) = (3, 5, 20, 18, 1, 6, 30) and deadlines (d1, d2, ........., d7) = (1, 3, 4, 3, 2, 1, 2)
4 M
2 (c)
Obtain a set of optimal Huffman codes for the messages (M1, M2, ..... M6) with relative frequencies (q1, q2, ....... q6) = (2, 3, 5, 7, 9, 13). Draw the decode tree for this set of codes.
8 M
Answer any one question from Q3 and Q4
3 (a)
Let n = 3 and {k1, k2, k3} = {do, if, while} Let p (1:3) = {0.5, 0.1, 0.05} Let q (0:3} = {0.15, 0.1, 0.05, 0.05} Compute & construct OBST for above values.
9 M
3 (b)
State multistage graph problem and explain how it can be solved using forward approach.
7 M
4 (a)
Explain 0/1 Knapsack 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 | 9 | 8 | 8 |
| 12 | 0 | 13 | 6 |
| 10 | 9 | 0 | 5 |
| 20 | 15 | 10 | 0 |
8 M
Answer any one question from Q5 and Q6
5 (a)
What are implicit and explicit constraints with respect to backtracking?
8 M
5 (b)
Write the control abstraction for LC-Search. Explain how Travelling Salesperson problem is solved using LCBB.
8 M
6 (a)
Write recursive algorithm on Graph Colouring using Backtracking Strategy. Determine the time complexity of the same.
8 M
6 (b)
Write an iterative 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)
Prove that vertex cover problem is NP complete.
9 M
7 (b)
Show that the sum of subsets problem is NP-Hard, given that Exact cover problem is NP-Hard.
9 M
8 (a)
What is meant by a problem 'reducing to' another problem? Prove that the clique decision problem reduces to node cover decision problem.
8 M
8 (b)
Explain NP-Hard scheduling problem with example. Also comment on the time complexity.
10 M
Answer any one question from Q9 and Q10
9 (a)
Write an algorithm for Odd-Even merge. Determine its time complexity.
8 M
9 (b)
Consider the following expression:
((7 - (21 / 3)) * 3) + ((9 * (10 - 8)) + 6) Explain how it can be evaluated parallel.
((7 - (21 / 3)) * 3) + ((9 * (10 - 8)) + 6) Explain how it can be evaluated parallel.
8 M
10 (a)
Explain how graph problems can be solved using parallel processors.
8 M
10 (b)
Explain in detail parallel MERGE sorting.
8 M
Answer any one question from Q11 and Q12
11 (a)
Explain Deadlock detection and avoidance algorithm.
8 M
11 (b)
What is meant by heuristic algorithms? Discuss any one heuristic search algorithm.
8 M
12 (a)
Explain convex hull algorithm. Comment on the time complexity.
8 M
12 (b)
Explain resource allocation algorithm for deadlock avoidance.
8 M
More question papers from Design & Analysis of Algorithms