Jawaharlal Nehru Technological University Hyderabad 2010-3rd Sem M.C.A -ester Supplementary s/ust DESIGN AND ANALYSIS OF ALGORITHMS - Question Paper

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA-III Semester Supplementary exams July /August2010
DESIGN AND ANALYSIS OF ALGORITHMS
Time: 3hours Max.Marks:60
ans any 5 ques.
All ques. carry equal Marks

1.(a) describe time complexity. define various notations used to represent these
complexities.
(b) discuss the Heap sort with an example.
2.(a) Write the Quick sort algorithm.
(b) Analyze the time complexity of Quick sort algorithm.
(c) Perform the quick sort to sort the subsequent numbers.
20, 40, 50, 15, 10, 05, 80, 90.
3.(a) Write an algorithm to implement Kruskal's algorithm for minimum spanning tree.
(b) Analyze the time complexity of Kruskal's algorithm.
4.(a) discuss the 0/1 knapsack issue with example.
(b) discuss how the traveling sales person issue can be solved using dynamic
programming frame work.
5.(a) discuss the BFS algorithm with an example.
(b) Write a non-recursive algorithm of In-order traversal of a tree and also analyze its
time complexity.
6.(a) Write an algorithm of m-coloring issue.
(b) discuss 'sum of subsets' algorithm with example.
7.(a) explain about LC search.
(b) explain FIFO Branch and Bound.
8. Write short notes on the subsequent
a) Cooks theorem
b) NP- hard
c) NP- complete

Earning:   Approval pending.