# VTU Previous Exam Papers BE CS 4th Semester Analysis and Design of Algorithms Jan 2008

# VTU Previous Exam Papers BE CS 4th Semester

# Analysis and Design of Algorithms Jan 2008

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

1 a. What do you mean by a stable algorithm and an algorithm is inplace? Explain the same and give an algorithm to sort a given list of numbers which should be stable but not inplace

b. What are the differences between set and multiset? Compare it with list. Explain with example two ways of defining sets.

c. Give three different algorithms to compute gcd of given two positive numbers and comment on their performance.

2 a. Define the commonly encountered asymptotic notations and illustrate with figures. Express the following functions using asymptotic notations : i) 6*2^{n} + n^{2} ii) j^n(n-l) Give the necessary steps to prove the same.

b. Give the general plan for analyzing the recursive algorithms. Mathematically analyse the tower of Hanoi problem, clearly indicating the steps and comment on its complexity.

3 a. What is brute force method? Explain the exhaustive search technique. How would you apply it to a job assignment problem? Explain with suitable example. Analyse for complexity.

b. Give the general divide and conquer recurrence and explain the same. Give the Master’s theorem and explain with example how would you apply it to solve the recurrence.

c. Using complexity analysis prove that Strassen’s matrix multiplication algorithm is more efficient compared to conventional matrix multiplication for large values of n. (06 Marks)

4 a. Explain the concepts of divide and conquer methodology indicating three major variations of same.

b. With suitable example explain Johnson trotter algorithm to generate permutation of given objects.

c. Give BFS and DFS algorithm. Clearly bring out the differences and comment on the complexity.

5 a. What is an AVL tree? Explain four types of rotations used to construct AVL tree. Construct an AVL tree for the list 5, 6, 8, 3, 2, 4, 7 showing clearly successive insertions.

b. What is a heap? Give an algorithm to construct a heap for the elements of given array by bottom up approach. What is its complexity? Show heap construction for the given list 2, 9, 7, 6, 5, 8 stage by stage.

6 a. With suitable example explain Boyer-Moore algorithm used in string matching. (08 Marks) b. Explain the concept of dynamic programming. With a suitable example explain an algorithm to solve all pair shortest path problem. Discuss about its complexity.

7 a. Justify the statement “Prim’s algorithm always yields minimum cost spanning tree”. Give the Prim’s algorithm and discuss about its complexity.

b. What is a Huffman tree? Explain it with suitable example and give Huffman’s algorithm.

c. Give Dijkstra’s algorithm. What is its complexity? Discuss with a simple example.

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

b. Write notes on :

i) Branch and bound method ii) P, NP and NP complete problems.