Download Model question papers & previous years question papers
|
Posted By: yamini Member Level: Gold Posted Date: 12 May 2008
|
2007 Jawaharlal Nehru Technological University B.Tech Computer science and engineering II II design and analysis of algorithms aug/sep 2007 set IV Question paper
|
|
|
Code No: R05220502 Set No. 4
II B.Tech II Semester Supplimentary Examinations, Aug/Sep 2007
DESIGN AND ANALYSIS OF ALGORITHMS
(Computer Science & Engineering)
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks
? ? ? ? ?
1. (a) Define omega notation. Explain the terms involved in it. Give an example.
(b) Show that f1(n)×f2(n) = 0(g1(n)×g2(n) wheref1(n) = 0(g1(n) and f2(n) =
0(g2(n)). [10+6]
2. (a) Write and explain the control abstraction for Divide and conquer.
(b) Suggest refinements to mergesort to make it in-place. [8+8]
3. (a) What is spanning tree? Explain the prim’s algorithm with an example.
(b) Explain the terms Feasible solution, optimal solution and objective function.
[10+6]
4. (a) Explain the OBST algorithm.
(b) Find the shortest tour of a TSP for following instance using dynamic program-
ming
(c)
A B C D
A inf 12 5 7
B 11 inf 13 6
C 4 9 inf 18
D 10 3 2 inf
[8+8]
5. (a) Explain the properties of depth-first search.
(b) Write a non-recursive algorithm of Post-order traversal of a tree and also
analyze its time complexity. [6+10]
6. (a) Draw the state space tree for m coloring when n=3 and m=3
(b) Write a recursive backtracking algorithm. [8+8]
7. Write the LCBB algorithm for the 0/1 Knapsack problem. Also Analyse its com-
plexity. [16]
8. (a) Explain the classes of NP-hard and NP-complete.
(b) Describe clique decision problem and write the algorithm for the same. [8+8]
Return to question paper search
|
|
|
Submit Previous Years University Question Papers and
make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.