B.Tech Degree Examination
Model Quesion Paper
13.603 DESIGN AND ANALYSIS OF ALGORITHMS (R)
Time: 3 Hrs Marks: 100
Answer all questions1. Why is more emphasis given to minimize the execution time of an algorithm rather than
the space requirement of an algorithm or computer program most of the time.
2. Demonstrate using a suitable example as to why raw computational power alone cannot
be a substitute for efficient algorithm design.
3. Explain master method for solving recurrence relations.
4. Why are height balanced trees used instead of ordinary binary search trees?
5. What sorting algorithm would you prefer to use if you know that most of your input are
already sorted? Why?(5X4=20 Marks)
Answer any one full question from each module.
6. a. Explain with an example how recurrence trees can be used to solve a recurrence
relation. 5 Marks
b. Solve the recurrence 2 / 4 T n( ) + n using methods based on
(i) Substitution (ii) Recursion tree (iii) Master theorem 15 Marks
7. a. Is a randomized algorithm for quicksort more efficient? Explain. 5 Marks
b. Write an algorithm to sort an array in decreasing order using Quicksort. Derive the
worst case running time for his algorithm. 15 Marks
8. a. With examples of your own show how union by rank and path compression heuristics
improve the running time to perform operations on Disjoint Set data structures. 10
b. Why are rotations performed on a Red-Black Tree? Write the Pseudocode to perform a
right rotate operation. Show the running time for the algorithm. 10 Marks
9. a. Why is a minimum degree of 1 disallowed in a B-Tree. Without any formal
pseudocode explain how a new node can added to a B-Tree. Use suitable examples for
clarity wherever necessary. 10 Marks
b. Explain how a node can be added to an AVL-Tree. 10 Marks
working using a suitable example. How does the Prim’s algorithm for minimum spanning
tree differ from Dijkstra’s shortest path algorithm?
11. a. Demonstrate how Strassen’s matrix multiplication method works by finding the
product of the given matrices:- 10 Marks
b. Does Merge Sort have a best case or worst case? Show the running the time for Merge
Sort. 10 Marks
12. a. What does the term “reducibility” mean? When do you say one language is polynomial
time reducible? 4 Marks
b. Explain the 8 Queen Problem. 10 Marks
c. What is the difference between the Travelling Salesperson Problem and Shortest Path Problem?
13. a. Use Dynamic Programming to solve the Matrix Chain Multiplication Problem.
b. What is greedy choice property? Write a solution for fractional knapsack problem
using greedy approach. 10 Marks