Osmania University (OU) 2007 B.E Computer Science and Engineering Design and Analysis of Algorithms - Question Paper
FACULTY OF ENGINEERING B. E. 3/4 (CSE) II Semester Main Examination, April/May 2007 DESIGN AND ANALYSIS OF ALGORITHMS
Time3 Hours] [Maximum Marks75
Answer ALL questions of Part-A.
Answer any FIVE questions from Part-B.
PART-A (Marks : 10x2-5=25)
1. What are different notations used for algorithm analysis ? Explain briefly.
2. Write control abstraction of greedy method.
3. Explain about mergable heap.
4. Write about NP-hard and NP-completeness problem.
5. Explain about hashing.
6. State Cook's theorem.
7. State travelling sales person problem.
8. State node covering problem.
9. What is dynamic programming ? Explain.
10. Write about knapsack problem.
PART-B (Marks : 5x10=50)
11. (a) Explain the Prim's algorithm.
(b) Explain about optimal storage on tapes.
12. (a) Describe merge sort algorithm.
(b) Write UNION and FIND algorithms.
13. (a) Describe the procedure to insert an element into a heap with an example.
(b) Solve the 0/1 - knapsack problem by considering the instant N=3, (wl, w2, w3) = (2,3,4), (pi, p2, p3) =(1,2,5) and capacity (m) = 6.
14. (a) Write greedy algorithm for job sequencing with deadlines.
(b) What is Hamiltonian cycle ? Give an example.
15. (a) Write an algorithm for the all pairs shortest path problem.
(b) Write an algorithm to generate next colour in M colouring problem.
16. (a) Explain the reliability design with an example.
(b) Write optimal binaiy search tree algorithm.
17. (a) Write backtracking algorithm for n-queens problems.
(b) What is branch and bound strategy ? Explain.
|
Attachment: |
| Earning: Approval pending. |
