**B.Tech Degree Examination**

**Model Quesion Paper**

**13.603 DESIGN AND ANALYSIS OF ALGORITHMS (R)**

**Time: 3 Hrs Marks: 100**

**PART A**

*Answer all questions*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)

**PART B**

**Answer any one full question from each module.**

**Module 1**

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

OR

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 9

12 15

4 12

6 11

**Module 2**

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

Marks

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

OR

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

**Module 3**

working using a suitable example. How does the Prim’s algorithm for minimum spanning

tree differ from Dijkstra’s shortest path algorithm?

20 Marks

OR

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

Module 4

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?

6 Marks

**OR**

13. a. Use Dynamic Programming to solve the Matrix Chain Multiplication Problem.

10 Marks

b. What is greedy choice property? Write a solution for fractional knapsack problem

using greedy approach. 10 Marks

## 0 comments