Jawaharlal Nehru University (JNU) 2008 M.C.A DESIGN AND ANALYSIS OF ALGORITHMS - Question Paper

2008 Jawaharlal Nehru Technological University M.C.A Computer Aplications DESIGN AND ANALYSIS OF ALGORITHMS - ques. paper

M.C.A IV Semester Supply Examinations, Apr/May -2008. DESIGN AND ANALYSIS OF ALGORITHMS Time: three hours

OR

Max. Marks: 60 ans any 5 ques. All ques. carry equal marks ---

1) What is meant by time complexity and space complexity? explain its importance. discuss the Heap sort with an example.

2) discuss the merge sort. Perform the quick sort to sort the subsequent numbers. 20 40 50 15 10 05 80 90.

3) explain about job sequencing with deadlines. What is meant by minimum spanning tree? explain how to achieve it?

4) discuss in detail the floor shop scheduling. explain the 0/1 knapsack issue.

5) discuss the breadth 1st search and traversal with a suitable example.

6) discuss the Hamiltonian cycles with a suitable example. What is meant by graph coloring? explain its uses.

7) explain about LC search. explain about non-deterministic algorithms.

Write short notes on the subsequent a) Cooks theorem b) Travelling sales man issue c) NP- complete

Earning:   Approval pending.