ANALYSIS OF ALGORITHMS (AOA) DECEMBER 2011 COMPUTER AND SCIENCE SEMESTER 4
Con. 6785-11. MP-4342
(3 Hours) [ Total Marks : 100 ]
N.B : (1) Question No.1 is compulsory.
(2) Out of remaining 6 questions attempt any 4 questions.
(3) In all 5 questions to be attempted.
Q.1. (a) | Compare the time complexities of the following algorithm giving their | 05 |
| complexities in terms of big -0,Ώ,Ө. | ||
| (i) Quick sort (iii) Heap sort | ||
| (ii) Shell sort (iv) Insertion sort. | ||
| (b) | State the applications of the Graph theory. | 05 |
| (c) | State advantages and disadvantages of recursion. | 05 |
| (d) | Write a routine to delete a word from a tries. | 05 |
Q.2. (a) | What is Hamiltonian Cycle? Write an algorithm to find all Hamiltonian Cycles. | 10 |
| (b) | Calculate variable length Huffman code for following frequencies | 10 |
A=2, B=6, C=4, D=15, E=7, F=22, G=9, H=17. | ||
Q.3. (a) | Explain 8-queen problem. Write an algorithm using backtracking to solve this | 10 |
| problem. | ||
| (b) | Explain graphing coloring algorithm with an example. | 10 |
Q.4. (a) | Write an algorithm for 0/1 knapsack problem using dynamic programming | 10 |
| approach. | ||
| (b) | Find the minimum cost spanning tree for the following graph using prim's | 10 |
algorithm. | ||
Q.5. (a) | What is travelling Salesman Problem? How to solve the same problem using | 10 |
| Branch and bound?Explain with example. | ||
| (b) | Sort the following list of elements in ascending order using merge sort | 10 |
| technique. Give the output of each pass. | ||
90 20 80 89 70 65 85 74. | ||
Q.6. (a) | Write functions to implement DFS and BFS graph searching methods. | 10 |
| (b) | To implement the binary search, prove that the complexity of binary search is | 10 |
| 0(log2n). | ||
Q.7. | Write short note on: | 20 |
| (a) Randomized Algorithms | ||
| (b) Divide and Conquer Strategy | ||
| (c) Optimal Storage on Tape | ||
| (d) Strassen's Matrix Multiplication. |
No comments:
Post a Comment