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(n

^{3}-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