MCSCS102/MCSCB102 Advanced Data Structures & Algorithms M.Tech Model Question Paper : mgu.ac.in

Name of the College : Mahatma Gandhi University
Department : Computer Science and Engineering
Subject Code/Name : MCSCS 102/ MCSCB 102/ADVANCED DATA STRUCTURES AND ALGORITHMS
Sem : I
Website : mgu.ac.in
Document Type : Model Question Paper

Download Model/Sample Question Paper :
I : https://www.pdfquestion.in/uploads/mgu.ac.in/5019-1-MCSCS,%20MCSCB%20102%20Advanced%20Data%20Structures%20and%20Algorithms%20Set1(1).doc
II : https://www.pdfquestion.in/uploads/mgu.ac.in/5019-2-MCSCS,%20MCSCB%20102%20Advanced%20Data%20Structures%20and%20Algorithms%20Set2(1).doc

MGU Advanced Data Structures Question Paper

M.TECH. DEGREE EXAMINATION :
Branch: Computer Science and Engineering
Specialization:

Related / Similar Question Paper :
MGU Natural Language Processing Question Paper

1. Computer Science and Engineering
2. Cyber Security

Paper – I

First Semester :
MCSCS 102/ MCSCB 102 : ADVANCED DATA STRUCTURES AND ALGORITHMS
(Regular – 2013 admission)
Time: 3 Hours
Max Marks: 100
Answer the following Questions. :
1. a) Explain how merging and splitting operations is done on a Splay Tree. (10)
b) Explain insertion and deletion algorithms in Red-Black trees with examples (15)
or
2. a) Explain insertion and deletion of elements in suffix trees with suitable examples (15)
b) Differentiate Binary Tries and Multiway Tries (10)

3. a) Explain single ended priority queue operations (10)
b) What are Binomial Heaps? What are its applications? (10)
c) Explain about Interval Heaps (5)
or
4. a) Explain insertion and deletion to double ended priority queue (15)
b) What is a leftist tree? Explain its insertion. (10)

5. a) Explain recursion tree method and Substitution method for solving recurrence with suitable examples. (15)
b) Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = 3 T(n/2) + n. Use the substitution method to verify the answer. (10)
or

6. a) Find an optimal parenthesization of a matrix chain product whose sequence of dimension is {5,10,3,12,5,20,6} (10)
b) Explain the computation of longest common subsequence problem (15)
or

7. a) Explain and analyze ford-fulkerson algorithm for maximum flow (15)
b) Discuss Edmond-karp algorithm for maximum flow (10)
or
8. a) Explain line segment properties computational geometry algorithms (10)
b) Discuss the strategies for finding the convex hull (15)

Paper – II

MCSCS 102/ MCSCB 102
ADVANCED DATA STRUCTURES AND ALGORITHMS :
(Regular – 2013 admission)
Time: 3 Hours
Max Marks: 100
Answer the following Questions. :
1. a) Explain insertion and deletion algorithms on threaded binary trees (15)
b) Write notes on Red-Black Trees and Splay Trees (10)
or

2. a) Explain insertion algorithm to Red-Black tree and insert the following keys:40,10, 30, 35, 25, 27, 26, 60, 55,61,80 (15)
b) Explain different types of tries (10)

3. a) Define height-biased min leftist trees. Give an algorithm to meld two such trees that takes O(log n) time. (10)
b) Explain any 3 types of heaps and their insertion (15)
or
4. a) Discuss double ended priority queue operations (10)
b) Explain insertion and deletion algorithms for Symmetric Min-Max Heaps with examples (15)

5. a) Explain master theorem for with suitable example (10)
b) Prove the three cases of master theorem (15)
or
6. a) Discuss dynamic rod-cutting top down and bottom up approaches (10)
b) Explain the computation of optimal cost for matrix chain multiplication (15)

7. a) Show that maximum flow in a network G = (V,E) can always be found by a sequence of at most | E | augmenting paths (10)
b) Discuss and analyze maximum bipartite matching algorithm (15)
or
8. a) Show how to determine in O(n2log n) time whether any three point in a set of n point collinear (10)
b) Explain and analyze the algorithm for finding the closest pair of points (15)

Syllabus

Module 1:
Trees – Threaded Binary Trees, Selection Trees, Forests and binary search trees, Counting Binary Trees, Red-Black Trees, Splay Trees, Suffix Trees, Digital Search Trees, Tries- Binary Tries, Multiway Tries

Module 2:
Priority Queues – Single and Double Ended Priority Queues, Leftist Trees, Binomial Heaps, Fibonacci Heaps, Pairing Heaps, Symmetric Min-Max Heaps, Interval Heaps

Module 3:
Analysis of Algorithms-review of algorithmic strategies, asymptotic analysis, solving recurrence relations through Substitution Method, Recursion Tree, and Master Method Dynamic Programming- Rod cutting-top down and bottom up approach, matrix chain multiplication-recursive solution, Longest common subsequence problem

Module 4:
Maximum Flow-Flow Networks, Ford-Fulkerson method-analysis of Ford-Fulkerson, Edmonds-Karp algorithm, Maximum bipartite matching
Computational Geometry- Line segment properties, Finding the convex hull , Finding the closest pair of points.

References:
1. Ellis Horowitz, Sartaj Sahni, Susan Anderson Freed, Fundamentals of Data Structures in C, Second Edition, University Press, 2008
2. Yedidyah Langsam, Moshe J. Augenstein, Aaron M. Tenenbaum, Data Structures using C and C++, Second Edition, PHI Learning Private Limited, 2010

3. Thomas Cormen, Charles, Ronald Rives, Introduction to algorithm,3rd edition, PHI Learning
4. Ellis Horowitz and Sartaj Sahni, Sanguthevar Rajasekaran, Fundamentals of Computer Algorithms,Universities Press, 2nd Edition, Hyderabad .