B.
Tech CSE
(SEM- V) ODD SEMESTER THEORY EXAMINATION
DESIGN & ANALYSIS OF ALGORITHMS
Time: 3 Hours Total Marks: 100
Note: (i) Attempt all questions.
(ii) All questions carry equal marks.
(iii) Be precise in your answer.
(iv) No second answer book will be provided.
(v) Make suitable assumptions, if required.
1. Attempt any two parts of the following: 10×2=20
(a) (i) What is time complexity? Analyze time complexity of Binary Search algorithm.
(ii) Solve the recurrence relation shown below:
T (n) = 7*T (n/2) + an2 if n ˃ 2
=b if n ≤ 2
(b) Give the algorithm for Heap Sort and discuss its time complexity. Illustrate the min heap
tree for following data : 30,46,5,4,23,81,90,43,1,13,72.
(c) (i) Write a short note on Asymptotic Notations.
(ii) Is 2n+1 = O (2n)? Is 22n = O (2n)?
2. Attempt any two parts of the following: 10×2=20
(a) (i) Explain the Red-Black(R-B) tree. Prove that a Red-Black tree with n internal nodes
has height at most 2 log(n+1).
(ii) Say a node x is inserted into a R-B tree with R-B insert and then immediately
Deleted with R-B Delete. Is the resulting R-B tree the same as the initial R-B tree? Justify
your answer.
(b) Write an algorithm for Binomial-Heap Union and also explain it with a suitable example.
(c) Construct a B-tree corresponding to following insertions 1, 2, 3, 4, 5, 6, 7, 8, 9,
10. Considering Fan out = 4.
3. Attempt any two parts of the following: 10×2=20
(a) What do you mean by Dynamic Programming? Describe the principle of Optimality.
Describe Travelling Sales Person Problem in brief.
(b)
Jobs J1 J2 J3 J4 J5 J6 J7 J8 J9
Profits 15 20 30 18 18 10 23 16 25
Deadlines 7 2 5 3 4 5 2 7 3
Here jobs are from J1………..J9. The execution time of each job is required 1 unit of time. You
can calculate one job at a time. Each job Ji has profit Pi and deadline di. You will get profit
Pi, if job Ji is completed before end of deadline di. What is the maximum profit?
(c) Write short notes on following:
(i) Amortized Analysis.
(ii) Branch-and-Bound.
4. Attempt any two parts of the following: 10×2=20
(a) Define Spanning Tree with example. Find the minimum cost spanning tree for following
graph by using Kruskal Algo.
10
A B
70 40 30
C 20 D
60 50
(b) Give the Dijkstra’s Algorithm for single source shortest path. Give a counter example
that shows that Dijkstra’s algorithm may not work for a weighted connected graph with
negative weight.
(c) Define Depth First Search. Write an algorithm for DFS, discussing its time complexity
also illustrates with some example.
5. Attempt any two parts of the following: 10×2=20
(a) (i) Discuss the decision problem class P and NP.
(ii) Discuss NP complete problem.
(b) Define String Matching Problem and describe any string matching algorithm in detail.
(c) Write short notes on following:
(i) Approximation algorithms.
(ii) DFT and FFT.
