Download PTU M.Tech IT 2nd Semester 72885 ADVANCED DATA STRUCTURES Question Paper

Download PTU. I.K. Gujral Punjab Technical University (IKGPTU) M.Tech IT 2nd Semester 72885 ADVANCED DATA STRUCTURES Question Paper.

1 | M-72885 (S9)-813
Roll No. Total No. of Pages : 02
Total No. of Questions : 08
M.Tech.(IT)(2015 & Onwards) E2 / (CSE Engg.) (2015 to 2017) (Sem.?2)
ADVANCED DATA STRUCTURES
Subject Code : MTCS-201
M.Code : 72885
Time : 3 Hrs. Max. Marks : 100

INSTRUCTION TO CANDIDATES :
1. Attempt any FIVE questions out of EIGHT questions.
2. Each question carries TWENTY marks.

1. a) How a data structure may be augmented? Explain.
b) Explain covering and partitioning in graphs with suitable examples.
2. a) Write an algorithm for graph coloring.
b) What are maximum flow problems? Write an algorithm to solve the problem.
3. a) Show the red-black trees that result after successively inserting the keys
41,38,31,12,19,8 into an initially empty red-black tree.
b) Explain the concepts of NP, NP-Hard and NP completeness.
4. a) What is the relationship among P, NP and NP complete problems? Show with the
help of a diagram.
b) Explain the working of Boyce-Moore string matching algorithm.
5. a) Explain deletion of a node in a Fibonacci heap with example.
b) Explain extraction of minimum element in a Fibonacci heap.
6. a) How are the graphs represented in the memory of a computer? Compare the graph
representation methods.
b) Modify the Dijkastra?s algorithm to solve all-pairs-shortest-path problem.

FirstRanker.com - FirstRanker's Choice
1 | M-72885 (S9)-813
Roll No. Total No. of Pages : 02
Total No. of Questions : 08
M.Tech.(IT)(2015 & Onwards) E2 / (CSE Engg.) (2015 to 2017) (Sem.?2)
ADVANCED DATA STRUCTURES
Subject Code : MTCS-201
M.Code : 72885
Time : 3 Hrs. Max. Marks : 100

INSTRUCTION TO CANDIDATES :
1. Attempt any FIVE questions out of EIGHT questions.
2. Each question carries TWENTY marks.

1. a) How a data structure may be augmented? Explain.
b) Explain covering and partitioning in graphs with suitable examples.
2. a) Write an algorithm for graph coloring.
b) What are maximum flow problems? Write an algorithm to solve the problem.
3. a) Show the red-black trees that result after successively inserting the keys
41,38,31,12,19,8 into an initially empty red-black tree.
b) Explain the concepts of NP, NP-Hard and NP completeness.
4. a) What is the relationship among P, NP and NP complete problems? Show with the
help of a diagram.
b) Explain the working of Boyce-Moore string matching algorithm.
5. a) Explain deletion of a node in a Fibonacci heap with example.
b) Explain extraction of minimum element in a Fibonacci heap.
6. a) How are the graphs represented in the memory of a computer? Compare the graph
representation methods.
b) Modify the Dijkastra?s algorithm to solve all-pairs-shortest-path problem.

2 | M-72885 (S9)-813
7. a) A newspaper agent daily drops the newspaper to the area assigned in such a manner
that he has to cover all houses in respective area with minimum travel cost. Compute
the minimum travel cost. The area assigned to the agent where he has to distribute
newspaper is shown below :

FIG.1
b) What is NP Completeness? Is P = NP? Explain.
8. a) What are disjoint sets? How is the Union operation performed? Explain.
b) Design an AVL tree from the following nodes by inserting nodes one by one. Show
all the steps and rotations :
8,9,10,2,1,5,3,6,4,7,11,12







NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any
page of Answer Sheet will lead to UMC against the Student.
H
1
H
6
H
7
H
8
H
5
H
4 H
3
H
2
1
6
8
4
4
4
7
7
3
3
2
2
5
6
FirstRanker.com - FirstRanker's Choice