Idea Transcript
You are here: Home > Computer Science CSE > Design & Analysis of Algorithm All posts from mgu.ac.in
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 Sponsored Links:
You can now ask your questions about this question paper. Please go to the bottom of this page.
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
Advanced Data Structures & Algorithms : M.TECH. DEGREE EXAMINATION : Branch: Computer Science and Engineering Specialization:
Related : MGU MCSCS106-3 Natural Language Processing M.Tech Model Question Paper : www.pdfquestion.in/5017.html
1. Computer Science and Engineering 2. Cyber Security Model Question Paper – II 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) 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 . Author : Anusha