 MORE IN Design & Analysis of Algorithms
SPPU Computer Engineering (Semester 7)
Design & Analysis of Algorithms
December 2015
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

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