**VTU Previous Exam Papers BE CS 4th Semester **

**Analysis and Design of Algorithms July 2006**

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

1 a. With a neat diagram, briefly explain the design and explain the design and analysis of an algorithm.

b. Explain what property of the adjacency matrix of an undirected graph indicates that the graph is complete has loop / has an isolated vertex.

c. Design a recursive algorithm for computing 2^{n} for a non negative integer n, based on the formula 2^{n} = 2^{n}‘^{1}+2^{11}“^{1}. Set up a recurrence relation for the number of additions made by the algorithm and solve it. For n = 5, draw a tree of recursive calls for this algorithm and count the number of calls.

2 a. Explain how we can compare the order of growth of 2 functions using limits. Compare order of growth of log2ii and 4n .

b. Define asymptotic notations 0, 0, Q and prove that ^ n{n -1) e ${n^{2}).

c. Sort the list ‘QUESTION^{5} in alphabetical order using the Bubble Sort algorithm.

3 a. Write down an algorithm to search for a key in a given array, using linear search. Find its best, worst and average case efficiencies.

b. State whether li e following are true or false: n^{2} + n + 5 <e j, n^{2} +1 e 0(10000«), n^{2} + 5 e $(n^{2}) n^{2} +1 e Q(w). (02 Marks)

c. Apply Quick Sort to sort the list “QUESTION^{5} in alphabetical order. Draw the tree of the recursive calls made.

4 a. Write down a recursive algorithm to compute the number of leaves in a binary tree.

b. Prove the correctness of the above algorithm in Q4(a).

c. Write an algorithm for DFS and explain how it can be used to solve topological sorting problem, with an example.

5 a. Design a presorting — based algorithm to find the mode and determine its efficiency class.

b. Construct an AVL tree by inserting the elements successively, for 3,6,5,7,1,2,8,4, staring from an empty tree.

c. Write down an algorithm to construct a heap by bottom-up method. Trace your algorithm for the list 1,8,6,5,3,7,4.

6 a. Construct a shift table for the pattern BAOBAB, and search for the same in the text BESS-KNEW-ABOUT-BAOBABS, using Horspoo Ps algorithm.

b. Briefly explain the dynamic programming technique using Floyd’s algorithm for the problem of all-pairs, shortest path as an example.

c. What are the requirements to be satisfied to apply greedy technique? Explain Prim ’ s algorithm with a suitable example. : ?

7 a. Construct a Huffman code for the following data: Character A B C D E Probability 0.4 0.1 0.2 0.14 0.16 Encode the text ABACABAD using the above code. Decode the text whose encoding is 100010111001010, using the above Huffman code

b. What is back tracking? Apply back tracing algorithm to solve the instance of the sum-of-subset problem S={1,3,4,5} and d~l 1.

c. With the help of a state-space tree, solve the following instance of the Knapsack problem by the branch-and-bound algorithm.

Item Weight Value

1 | 10 | 100 |

2 | 7 | 63 |

3 | 8 | 56 |

4 | /j | 12 |

8 a. What is the need for approximate algorithms? Explain, with a suitable example, the nearest neighbor algorithm.

b. Write down the decision tree for the three-element insertion sort.

c. Define the following: Decision problem, Class of NP problems, NP-Complete problem and Polemically reducible problems.