MORE IN Design & Analysis of Algorithms
SPPU Computer Engineering (Semester 7)
Design & Analysis of Algorithms
May 2017
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 Q.1(a,b,c) &Q.2(a,b,c)
1(a) Explain Big Oh (O), Omega(&Omgega;) And Theta(θ) notations in detail along with suitable examples.
6 M
1(b) Write an algorithm for Knapsack problem using Greedy Strategy.
6 M
1(c) Write a short note on 8-queens problem. Write algorithm for the same.
8 M

2(a) Calculate the Average case time complexity of f(n) = 3n(n2-n)+2n+5 using running time complexity.
6 M
2(b) Write an algorithm for optimum binary search tree.
6 M
2(c) Explain in detail backtracking strategy and give control abstraction for the same.
8 M

Solve any one question from Q.3(a,b) &Q.4(a,b)
3(a) Give and explain realtionship between P, NP, NP complete and NP Hard.
8 M
3(b) Explain Non-Deterministic clique problem along with algorithm.
8 M

4(a) Give and Explain Non-Deterministic sorting algorithm.
8 M
4(b) Prove that Vertex cover problem is NP-complete.
8 M

Solve any one question from Q.5(a,b) & Q.6(a,b)
5(a) Explain in detail Dining philosopher's problem.
8 M
5(b) Give and explain Minimum Spanning Tree algorithm.
8 M

6(a) Write an algorithm for finding Parallel shortest paths. Also comment on the time complexity of this algortihm.
8 M
6(b) Explain in detail with example Sequential and Parallel computing.
8 M

Solve any one question from Q.7(a,b) & Q.8(a,b)
7(a) Give and explain Dijkstra-Scholten algorithm.
9 M
7(b) Explain in detail Sorting algortihm for embedded Systems.
9 M

8(a) Write a short note on Internet of Things Algortihm.
9 M
8(b) Given and explain String matching algortihm.
9 M

More question papers from Design & Analysis of Algorithms