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

Roll No.

Total No. of Pages : 02

Total No. of Questions : 08

--- Content provided by⁠ FirstRanker.com ---

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.

--- Content provided by‌ FirstRanker.com ---

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.
   

   --- Content provided by‌ FirstRanker.com ---

   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. FirstRanker.com
   b) Explain the concepts help of a diagram, NP-Hard and NP completeness.

--- Content provided by FirstRanker.com ---

4. a) What is the relationship among P, NP and NP complete problems? Show with the 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.

--- Content provided by​ FirstRanker.com ---

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 :
   
   H1 4 7 5 6 H6 8 3 H2 3 H7 6 4 2 2 H5 7 4 H8 H3 H4 1 FIG.1
   
   b) What is NP Completeness? Is P = NP? Explain.

--- Content provided by FirstRanker.com ---

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.