Deemed University 2010 M.Tech Information Technology University: Lingayas University Term: III Title of the : Advanced Data Structure - Question Paper

Roll No. ..

 

Lingayas University, Faridabad

M.Tech (Part-Time) Information Technology

Term-III Examination May, 2010

Advanced Data Structure (IT-504)

[Time: 3 Hours] [Max. Marks: 100]

 

Before answering the question, candidate should ensure that they have been supplied the correct and complete question paper. No complaint in this regard, will be entertained after examination.

 

Note: Question No. 1 Section A is compulsory. Attempt any two questions from Section B and any two questions from Section C. In all attempt five questions.

Section A

Q-1

(i) Explain about NP-hard problems. (4)

(ii) What are the different types of complexities? Explain about the asymptotic notation. (4)

(iii) Distinguish between greedy and dynamic programming, (4)

(iv) How a general tree in converted into Binary Tree? Explain with example. (4)

(v) If in a complete binary tree there are 64 terminal nodes then calculate the total number of nodes in this. (4)

Section B

Q-2. Explain longest common sequence problem and write the algorithm for this. (20)

Q-3. What are two standard ways of maintaining a tree in the memory of a computer? Explain these. (20)

Q-4. Explain about AVL tree and B-tree. How the insertion operation is performed in these two? (20)

Section C

Q-5. Write the algorithm for topological sort and explain it with example. (20)

Q-6. What are the different methods of traversing a graph? Write the algorithm for these. (20)

Q-7. Explain Prims and Kruskals algorithm with suitable examples. (20)

Q-8. Find a path through a weighted graph which starts and ends at same vertex, including every other vertex exactly once, and minimizes the total cost of edges. (20)

Roll No. ..

 

Lingayas University, Faridabad

M.Tech (Part-Time) Information Technology

Term-III Examination May, 2010

Advanced Data Structure (IT-504)

[Time: 3 Hours] [Max. Marks: 100]

 

Before answering the question, candidate should ensure that they have been supplied the correct and complete question paper. No complaint in this regard, will be entertained after examination.

 

Note: Question No. 1 Section A is compulsory. Attempt any two questions from Section B and any two questions from Section C. In all attempt five questions.

Section A

Q-1

(i) Explain about NP-hard problems. (4)

(ii) What are the different types of complexities? Explain about the asymptotic notation. (4)

(iii) Distinguish between greedy and dynamic programming, (4)

(iv) How a general tree in converted into Binary Tree? Explain with example. (4)

(v) If in a complete binary tree there are 64 terminal nodes then calculate the total number of nodes in this. (4)

Section B

Q-2. Explain longest common sequence problem and write the algorithm for this. (20)

Q-3. What are two standard ways of maintaining a tree in the memory of a computer? Explain these. (20)

Q-4. Explain about AVL tree and B-tree. How the insertion operation is performed in these two? (20)

Section C

Q-5. Write the algorithm for topological sort and explain it with example. (20)

Q-6. What are the different methods of traversing a graph? Write the algorithm for these. (20)

Q-7. Explain Prims and Kruskals algorithm with suitable examples. (20)

Q-8. Find a path through a weighted graph which starts and ends at same vertex, including every other vertex exactly once, and minimizes the total cost of edges. (20)