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

 

 

 

 

Code No: 35

 

 

NR

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

MCA-III Semester Supplementary Examinations July /August2010

DESIGN AND ANALYSIS OF ALGORITHMS

Time: 3hours Max.Marks:60

Answer any Five questions

All questions carry equal Marks

---

 

1.(a)

 

(b)

 

2.(a)

(b)

Define time complexity. Describe different notations used to represent these

complexities.

Explain the Heap sort with an example.

 

Write the Quick sort algorithm.

Analyze the time complexity of Quick sort algorithm.

(c) Perform the quick sort to sort the following numbers.

20, 40, 50, 15, 10, 05, 80, 90.

 

3.(a) Write an algorithm to implement Kruskals algorithm for minimum spanning tree.

(b) Analyze the time complexity of Kruskals algorithm.

 

4.(a) Explain the 0/1 knapsack problem with example.

(b) Explain how the traveling sales person problem can be solved using dynamic

programming frame work.

 

5.(a) Explain 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 problem.

(b) Explain sum of subsets algorithm with example.

 

7.(a) Discuss about LC search.

(b) Discuss FIFO Branch and Bound.

 

8. Write short notes on the following

a) Cooks theorem

b) NP- hard

c) NP- complete

 

 

 

 

********