Visvesvaraya Technological University (VTU) 2006 B.E Computer Science ANALYSIS AND DESIGN OF ALGORITHM - Question Paper

1 a. With a neat diagram ,briefly discuss the design and analysis of an algorithm.
b. discuss what property of the adjacency matrix of an undirected graph shows that the graph is complete has loop/ has an isolated vertex.
c. Design a recurssive algorithm for computing 2^n=2^n-1 + 2^n-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 numbert of calls.

2 a. discuss how we can compare the order of growth of two functions using limits. Compare order of growth of log to the base two n and root n.
b. describe assymptotic notations O,theta,omega and prove that 1/2 n(n-1) belongs to theta(n^2).
c. Sort the list 'QUESTION' in alphabetical order using the bubble sort algorithm.

3 a. Write down an algorithm to search for a key in a provided array , using linear search. obtain its best worst and avg. case efficiencies.
b. State whether the subsequent are actual or false:
n^2 + n + five belongs to O(n^3) , n^2 +1 belongs to O(1000n) , n^2 + five belongs to theta(n^2) , n^2 +1 belongs to omega(n).
c. Apply Quick sort to sort the list in alphabetical order. Draw the tree of the recurssive calls made.

4 a. Write down a recursive algorithm to calculate 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 discuss how it can be used to solve topological sorting issue with an example.

5 a. Design a presorting - based algorithm to obtain the mode and determine its efficiency class.
b. Construct an AVL tree by inserting the elements succesfully, for 3,6,5,7,1,2,8,4, starting from an empty tree.
c. Write down amn 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 trend BOABAB, and search for the identical in the text BESS-KNEW-ABOUT-BOABABS, using horsepool's
algorithm.
b. Briefly discuss the dynamic programming technique using floyd's algorithm for the issue of all-pairs, shortest path as an example.
c. elaborate the requirements to be satisfied to apply greedy technique? discuss Prim's algorithm with a suitable example.

7 a. Construct a huffman code for the subsequent 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 tracking algorithm to solve the instance of the sum - of- subset issue S= {1,3,4,5} and d=11.
c. With the help of a state-space tree ,solve the subsequent instance of the knapsack issue by the branch -and - bound algorithm.

ITEM WEIGHT VALUE
1 10 100
2 7 63
3 8 56
4 4 12

8 a. What is the need for approximate algorithms? discuss ,with a suitable example , the closest neighbour algorithm.
b. Write down the decision tree for the three-element insertion sort.
c. describe the subsequent :
Decision issue , Class of NP issues , NP -Complete issue and polynomially reducible issues.

Earning:   Approval pending.