ANALYSIS OF ALGORITHMS (AOA) MAY 2013 COMPUTER AND SCIENCE SEMESTER 4
Con. 6646-13. GS-7323
(3 Hours) [Total Marks : 100]
N.B. (1) Question No. 1 is compulsory.
(2) Attempt any four questions out of remaining six questions.
(3) Assume suitable data wherever necessary.
1. (a) | Explain Divide and Conquer strategy. Write control abstraction (General method) | 10 |
| for it. List any four examples that can be solved by divide and conquer. | ||
| (b) | Explain Asymptotic notations. Explain time complexity and space complexity in detail. | 10 |
2. (a) | Explain Graph coloring problem using backtracking. Write algorithm for same. | 10 |
| (b) | Find out single source shortest path for following graph using Dijkstra's algorithm. | 10 |
3. (a) | Find the longest common subsequence from the given two sequences :- | 10 |
| P= (100101101101) | ||
| Q= (0110) | ||
| (b) | Explain 15-puzzle problem using branch and bound. | 10 |
4. (a) | Sort following numbers using Quicksort algorithm. Show all passes of execution. | 10 |
| Also state the time complexity. | ||
| 65, 70, 75, 80, 85, 60, 55, 50, 45 | ||
| (b) | Explain and write Knunth-Morris pratt algorithm. Explain with an example. | 10 |
5. (a) | Explain job-sequencing with deadlines. Solve the following instance : | 10 |
| n = 5. | ||
| (P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1) | ||
| (d1, d2, d3, d4, d5) = (2, 2, 1, 3, 3) | ||
| (b) | Solve following sum of subset problem using backtracking : | 10 |
| w = { 1, 3, 4, 5 } | ||
| m = 8 | ||
| Find all possible subsets of 'w' that sum to 'm'. | ||
6. (a) | Solve shortest path from source 1 for following graph using dynamic | 10 |
programming. | ||
| (b) | Explain travelling salesperson problem using branch and bound method. | 10 |
7. | Write short notes :- | 20 |
| (a) Differentiate between greedy approach and dynamic programming. | ||
| (b) Optimal storage on tapes. | ||
| (c) Radix sort | ||
| (d) Minimum spanning Tree using Kruskal's Algorithm. |
No comments:
Post a Comment