# KTU B.Tech S6 Model Questions Design and Analysis of Algorithms CS

B.Tech Degree Examination

Model Quesion Paper

13.603 DESIGN AND ANALYSIS OF ALGORITHMS (R)

Time: 3 Hrs                                                             Marks: 100

PART A
1. 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

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

10. Explain how Prims algorithm successfully finds the minimum spanning tree. Illustrate it’s
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