Jawaharlal Nehru Technological University Kakinada 2010-3rd Sem M.C.A Subject Code: 35 [NR] Supplementary s, DESIGN AND ANALYSIS OF ALGORITHMS - Question Paper

Time: three Hours

Max Marks: 60


ans any 5 ques. All ques. carry EQUAL marks



1. What is meant by time complexity? explain about different notations of time complexity
with suitable example.

2. Demonstrate quick sort procedure through an example. Derive the best and worst case
time complexities for the quick sort algorithm.


3. a) discuss how the knapsack issue can be solved by the greedy method. elaborate the
various options of "greediness"?
b) discuss Prim's method of obtaining the minimum spanning tree using an example.


4. discuss how dynamic programming can be used to solve the subsequent Traveling sales
person issue.


ª- 20 30 10 11º

-
«3 five two four »
« »
«19 six 18 three »
«16 four seven 16 »


5. Suggest algorithms for breadth 1st and depth 1st search methods and compare their
performances.



6. Suggest a back tracking based algorithm to solve the eight queen's issue.


7. Suggest a FIFO branch and bound algorithm to obtain the lowest cost ans node.


8. Write short notes on:
a) NP Hard issue
b) AND/OR graphs
c) Graph coloring issue.

Earning:   Approval pending.