B.TECH - Semester 6 design and analysis of algorthims Question Paper 2013 (apr)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- What is recurrence relation? solve the recurrence relation $T(n)=2 T(n / 2)+n$ using substitution.
- What is space complexity? What is its importance?
- What is a B Tree? Explain with an Example.
- Write the algorithm for DFS traversal? Demonstrate its working with an example.
- Explain the complexity classes NP and NP Hard in detail. Name a problem which belongs to each these classes. ( $5 \times 4=20$ Marks) PART - B Answer one question completely from each module
- (a) Explain Master and Iteration method of solving recurrence relation with a suitable example for each method.
- (b) Explain any two Aysmptotic notations in detail.
- (a) Explain randomized algorithm for quick sort with an example.
- (b) Write the heap sort algorithm and demonstrate its working with a suitable. Example.
- (a) What is a Red Black Tree? Explain rotation operations on Red Black Trees.
- (b) What is an AVL Tree? Explain the insertion operation on AVL-Tree in detail covering all cases.
- (a) What is a set? Explain the of Union-Find algorithm with suitable example for Union and Find operation.
- (b) Compare Red-Black tree and AVL Tree, Give the complexity of insertion, deletion and search for both these trees.
- (a) Give the Kruskal's algorithm for Minimum Spanning Tree. What is its complexity?
- (b) Explain Divide and Conquer strategy with an example.
- (a) Explain why Strassen's Matrix Multiplication is better than general matrix multiplication method with a suitable example.
- (b) What is a Directed Acyclic Graph? Demonstrate the working of Topological Sort algorithm with a suitable example.
- (a) Explain dynamic programming based solution to Matrix Chain Multiplication problem. Explain its working with a suitable example.
- (b) What is 8 -queen Problem? Give the algorithm to solve this problem using Back Tracking.
- (a) What is Greedy strategy? Demonstrate its working in the case of any problem solvable using it.
- (b) Explain Branch and Bound strategy in detail. Compare it with dynamic programming strategy. ( $\mathbf{4} \boldsymbol{\times} \mathbf{2 0} \boldsymbol{=} \mathbf{8 0}$ Marks) ELEREACE - $\mathrm{OP}^{\mathrm{H}^{2}}$