Jawaharlal Nehru Technological University Hyderabad 2011-3rd Sem M.C.A Code No: 35 NR s- DESIGN AND ANALYSIS OF ALGORITHMS - Question Paper

1. a) What is time complexity? discuss the notations used to represent time complexity.
b) discuss the heap sort algorithm with an example.
2. a) discuss the control abstraction for the divide and conquer approach.
b) discuss the merge sort algorithm.
3. a) What is the greedy method for designing algorithms?
b) discuss how the greedy method can be used to obtain the optimal storage on tapes.
4. a) What is dynamic programming? discuss how this method differs from the greedy method.
b) define the 0/1 knapsack problem, and how the issue can be solved using the dynamic programming approach.
5. a) discuss the DFS method for tree traversal.
b) discuss a non-recursive algorithm for inorder traversal of binary tree.
6. a) discuss the control abstraction for backtracking.
b) define the 8-queens issue and an algorithm to solve the issue using backtracking.
7. a) define the LC search.
c) discuss FIFO branch and bound.
8. Write short notes on:
a) Cook's theorem
b) NP complete issues
c) Game trees

Earning:   Approval pending.