DESIGN AND ANALYSIS OF ALGORITHM Past Paper B,TEC 2016-17 UOS
Read and download DESIGN AND ANALYSIS OF ALGORITHM Past Paper B,TEC 2016-17 UOS
Paper ID: 2012264
B.Tech. Regular Theory Examination (Odd Sem – V) 2016-17
Subject: Design and Analysis of Algorithm
Time: 3 Hours
Max. Marks: 100
Section – A
Section – A
Attempt all parts. All parts carry equal marks. Write answer of each part in short. (10×2=20)
- a) List out the disadvantages of divide and conquer algorithm.
- b) What are the fundamental steps involved in algorithmic problem solving?
- c) Write recursive function to find nth Fibonacci number.
- d) Define Binary heap.
- e) Briefly explain the Prim’s algorithm.
- f) Define principle of optimality.
Section – B
Attempt any five questions from this section. (5×10=50)
- Explain the concepts of quick sort method and analyze its complexity with suitable example.
- Explain the concept of merge sort with example.
- Insert the nodes 15, 13, 12, 16, 19, 23, 5, 8 in empty Red-Black Tree and delete in the reverse order of insertion.
- Write short note on Dijkstra’s algorithm shortest paths – Dijkstra’s algorithm shortest path problems.
- Write pseudocode for 8 queen problem.
- Write non-deterministic algorithm for sorting.
- What is backtracking? Write general iterative algorithm for backtracking.
- Differentiate NP complete with NP hard.
Section C
- Instructions: Attempt any 2 questions from this section (2×15=30).
- (i) Bellman Ford algorithm statement. (ii) Knapsack problem solution using greedy method.
- Traveling salesman problem solution using branch and bound.
- Prove that the three coloring problem is NP Complete.
For more information on algorithms and their design and analysis, you can visit GeeksforGeeks.