STUPIDSID
Solve any one question from Q1 and Q2
1 (a)
Write control abstraction for Divide and Conquer Strategy and comment on its generalized recurrence equation.
6 M
1 (b)
Find an optimal solution for following 0/1 Knapsack problem using dynamic programming: Number of Objects n = 4, Knapsack Capacity M = 5, Weights (W1, W2, W3, W4) = (2, 3, 4, 5) and profits (P1, P2, P3, P4) = (3, 4, 5, 6).
6 M
1 (c)
Write a short note on graph coloring problem. Write algorithm for the
same.
8 M
2 (a)
Calculate the worst case time complexity of f(n) = 6n(n3-n)+9n using
running time complexity.
6 M
2 (b)
Write an algorithm for optimum binary search tree.
6 M
2 (c)
Explain in detail with one example Travelling Salesperson Problem using
branch and bound method.
8 M
Solve any one question from Q3 and Q4
3 (a)
Write non deterministic algorithm for Clique decision problem.
8 M
3 (b)
Prove that Vertex cover problem is NP Complete.
8 M
4 (a)
Write a short note on Randomized algorithm.
8 M
4 (b)
Write non deterministic algorithm for sorting elements in non-decreasing order.
8 M
Solve any one question from Q5 and Q6
5 (a)
Explain how graph problems can be solved using parallel algorithm.
8 M
5 (b)
Write Kruskal's algorithm using parallel computing to find minimum spanning tree. Explain with a suitable example.
8 M
6 (a)
Write an algorithm for finding Parallel shortest paths. Also comment on the time complexity of this algorithm.
8 M
6 (b)
Write an odd-even merge sort algorithm. Explain with a suitable example.
8 M
Solve any one question from Q7 and Q8
7 (a)
Give and explain Dijkstra-Scholten algorithm.
9 M
7 (b)
What is Embedded system? Explain Embedded system Scheduling.
9 M
8 (a)
Define Internet of things (IoT). Explain elements of IoT.
9 M
8 (b)
Give and explain Algorithms in Software Engineering with example.
9 M
More question papers from Design & Analysis of Algorithms