Name of the University : Mahatma Gandhi University
Department : Computer Science and Engineering
Degree : B.Tech
Subject Code/Name : CS010 601/Design And Analysis Of Algorithm
Sem : VI
Website : https://www.mgu.ac.in/home/
Document Type : Model Question Paper
Download Model/Sample Question Paper : https://www.pdfquestion.in/uploads/mgu.ac.in/5137-CS%20601.pdf
MGU Design & Analysis of Algorithm
B.TECH Degree Examination,May 2013 :
Model Question Paper :
Sixth Semester :
Related / Similar Question Paper :
MGU B.Tech UNIX Shell Programming Question Paper
Model Question Paper
Branch: Computer Science and Engineering
CS010 601 Design And Analysis Of Algorithm :
Time : Three Hours
Maximum : 100 Marks
Answer all the questions. :
Part A
Each question carries 3 marks. :
1. What is the need of obtaining the time and space complexity measures of an algorithm?
2. What is the notion behind divide and conquer method.
3. Write a note on multistage graph problem.
4. Explain the control abstraction for back tracking technique.
5. Differentiate between Deterministic and nondeterministic algorithm.
(5 x 3 = 15 marks)
Part B
Each question carries 5 marks. :
6. With the help of example explain how a recursive algorithm can be represented by recurrence relation.
7. Show the various steps involved in the quick sorting of (1,3,4,-5,9,2,6,5,3).
8. What is relevance of greedy method to solve knapsack problem.
9. Does an N Queens problem with 3X 3 board have a solution? How many solutions are there for the 8 queens problem?
10. Explain complexity of Kth element selection?
(5 x 5 = 25 marks)
Part C
Each question carries 12 marks.
11. What is difference between time and space complexity. Also describe asymptotic notations used for describing the complexity.
Or
12. Solve the following recurrence relations.
i) T(n)= 2T(n/2)+n log n ii) T(n)= 2T(n/3)+T(2n/3)+Cn
13. Explain merge sort algorithm and find the complexity of the algorithm.
Or
14. Explain the algorithm for finding maximum and minimum, and analyse its time complexity.
15. Explain Kruskal’s algorithm and its complexities.Analyse it with an example.
Or
16. Explain how to solve travelling salesman problem by the method of dynamic programming and analyse complexity of the algorithm.
17. State the 15 puzzle problem. How it is solved? What is the best method to solve the problem in terms of complexity?
Or
18. How to solve the sum of subset problem with explanation of its time complexity.
19. Prove that any algorithm that works by comparing keys to find the second largest from a set of n keys must do at least n+log n-2 comparisons in the worst case.
Or
20. Define string matching problem and describe any string matching algorithm in detail. (5 x 12 = 60 marks)
Syllabus
CS010 601 : Design And Analysis Of Algorithms (Common with IT010 605)
Objectives :
** To develop an understanding about basic algorithms and different problem solving strategies.
** To improve creativeness and the confidence to solve non-conventional problems and expertise for analysing existing solutions.
Module I : (13 hours)
Introduction and Complexity
What is an algorithm – Properties of an Algorithm, Development of an algorithm, Pseudocode Conventions, Recursive Algorithms – Performance Analysis – Space and Time Complexity –Asymptotic Notations – ‘Oh’, ‘Omega’, ‘Theta’, Worst, Best and Average Case Complexity, Running Time Comparison, Common Complexity Functions -Recurrence Relations – Solving Recurrences using Iteration and Recurrence Trees – Example Problems – Profiling – Amortized Complexity.
Module II : (11 hours)
Divide and Conquer – Control Abstraction, Finding Maximum and Minimum, Costs associated element comparisons and index comparisons, Binary Search, Divide and Conquer Matrix Multiplication, Stressen’s Matrix Multiplication, Quick Sort, Merge Sort. – Refinements.
Module III : (14 hours)
Greedy Strategy – Control Abstraction, General Knapsack Problem, Minimum Cost Spanning Trees – PRIM’s Algorithm, Kruskal’s Algorithm, Job sequencing with deadlines. Dynamic Programming – Principle of Optimality, Multistage Graph Problem, Forward Approach, Backward Approach, All-Pairs Shortest Paths, Traveling Salesman Problem.
Module IV : (11 hours)
Backtracking – State Space Tree – Fixed Tuple and Variable Tuple Formulation – Control Abstraction – Generating Function and Bounding Function – Efficiency of the method – Monte Carlo Method – N-Queens Problem, Sum of Subsets. Branch and Bound Techniques – FIFO, LIFO, and LC Control Abstractions, 15-puzzle.
Module V : (11 hours)
Sophisticated Algorithms – Approximation Algorithms – Planar Graph Coloring, Vertex cover – String Matching Algorithms – Rabin Karp algorithm – Topological Sort – Deterministic and Non-Deterministic Algorithms.
Lower Bound Theory – Comparison Trees for Searching and Sorting, lower bound on comparison based algorithms, Sorting, Selection & Merging; Oracles and Adversary Arguments –Merging,Basic concepts of randomized algorithm-Las Vagas algorithm for search.