# VTU Previous Exam Papers BE CS 4th Semester

# Analysis and Design of Algorithms Aug 2005

** ****Note: 1. Answer any FIVE full questions.**

**2. Algorithms should be accompanied by sufficient explanations.**

1. (a) Explain the various stages of algorithm design and analysis process with the

help of a flow chart.

(b) Define the terms sparse and dense with reference to graph. With suitable example explain the methods used to represent sparse and dense graphs comment on space complexity of each representation.

2. (a) Explain various asymptotic notations used in analysing algorithm. Give the

examples.

(b) If ^(n) e 0(g_{1}(rij) and ^(^{n}) € 0(g_{2}(n)) then prove the following assertion

*l(n) h.{^{n}) € 0[max{gi(n)^ g2(n)})

(c) With suitable example explain the significance of order of growth in analysing algorithms efficiency.

3. (a) Suggest general plan for analysing recursive algorithms. Mathematically

analyse the tower of hanoi problem and find its complexity.

(b) What is a brute force method? Write a brute force string matching algorithm. Explain with suitable example the correctness of that algorithm. Analyze for complexity.

4. (a) Explain the divide and conquer methodology. Suggest a pseudocode for merge-sort and analyse its complexities. Trace algorithm to the data set 8.4,1,6,7,2,3,9.

(b) Briefly explain Strassen’s matrix multiplication and how it uses divide and conquer method. Obtain its time complexity.

5. (a) With suitable example, explain depth first, search and breadth first search

algorithms. Write the pseudocodes for both. Derive the time-complexities. Explain its use in topological sorting.

(b) State Horspool’s algorithm for pattern matching. Apply it to search for the pattern BARBER in the given test ; consider all the 4 cases.

6. (a) Define the three variations of transform and conquer algorithms. Construct an AVL tree for the list 5,6,8,3,2,4,7 by successive insertions. State four rotation types used in the construction of ALV tree, and explain the same.

(b) Construct heap for the list 2,9,7,6,5,8 using bottom up construction algorithm. Explain clearly procedure of adding new element in that method. Explain in brief heap sort algorithm and obtain its complexity.

7. (a) Explain how dynamic programming is used to compute all pair shortest paths for a weighted digraph. Write the pseudo code for same and derive the time Complexity.

(b) Give Huffman’s algorithm to construct Huffman tree and explain same with suitable example.

(c) Using greedy method trace the following grpah to get shortest path from vertex a to all other vertices.

8. (a) Explain backtracking concept and apply same to n-queen’s problem

(b) Explain how TSP problem can be solved using branch and bound method.

(c) Write brief note on P. NP and NP-complete problems.