Wednesday, January 20, 2016

May 2015 Question Paper of Design and Analysis of Algorithms, MG University

Looking for MG University Design and Analysis of Algorithms old question papers. You can find here May 2015 Question Paper of Design and Analysis of Algorithms for MG University
Mahatma Gandhi University / MG University
May 2015 Question Paper
Course: B.Tech Computer Science and Engineering
Semester: 6
Subject Code: CS010 601
Subject: Design and Analysis of Algorithms
Time Duration: 3:00 hours
Full Marks: 100
Pass Marks: 40

Part A [5*3=15 marks]

1. What are asymptotic notations ? With a figure explain any two of them used for specifying best and worst-case complexities.

2. Using recurrence, derive the complexity of merge-sort algorithm. What is the method behind the algorithm ?

3. What is multistage graph problem ?

4. What is state space tree ? Give an example.

5. Give algorithm for topological sort.

Part B [5*5=25 marks]

6. State Master's Theorem for solving recurrence. Solve: (i) T(n)=3T(n/4)+nlogn by this method.

7. Using Divide and Conquer, give an algorithm for binary search.

8. Give Prim's algorithm for obtaining a minimum spanning tree. What is the loop-invariant in the algorithm ?

9. Explain Monte-Carlo Method.

10. Explain complexity of kth element selection.

Part C [5*12=60 marks]

11. (a) Define space and time complexity. Give an example. [4 marks]

(b) Define asymptotic upper bound of T(n)=2T(n/2)+n using substitution method. [4 marks]

(c) Use recursion tree to determine a good asymptotic upper bound on the recurrence T(n)=3T(n/2)+n. [4 marks]

OR

12. Write an algorithm to sort an array of n-elements using insertion sort and derive its best and worst case runtime complexities.

13. Explain quick sort algorithm. Derive its running time. Show the various steps in quick sorting of < 13, 4, -9, 25, 1, 6, 15, 32 >.

OR

14. Give Strassen's matrix multiplication method. Compare it with the usual matrix multiplication algorithm.

15. (a) What is principle of optimality ? [3 marks]

(b) Compare 0/1 Knapsack and fractional Knapsack problem. [4 marks]

(c) Explain job sequencing with deadlines. [5 marks]

OR

16. (a) What is greedy strategy ? [3 marks]

(b) Give a greedy solution for Knapsack problem. Can greedy method used for solving 0/1 Knapsack problem ? [5 marks]

(c) Compare Dynamic programming and divide and conquer method. [4 marks]

17. State the puzzle problem. What is the best method for solving it ? Also give its complexity.

OR

18. (a) Give FIFO and LIFO control abstractions in branch and bound method. [5 marks]

(b) What is backtracking ? Give any problem that can be solved by backtracking. [7 marks]

19. (a) Write short notes on deterministic and non-deterministic algorithms. [5 marks]

(b) How is comparison tree used in searching problems ? [4 marks]

(c) What is lower bound theory ? [3 marks]

OR

20. (a) Give Las-Vegas algorithm. [6 marks]

(b) Write the steps in Rabin-Karp algorithm. [6 marks]

Duraimani

B.E Civil Engineer Graduated from Government College of Engineering Tirunelveli in the year 2016. She has developed this website for the welfare of students community not only for students under Anna University Chennai, but for all universities located in India. That's why her website is named as www.IndianUniversityQuestionPapers.com . If you don't find any study materials that you are looking for, you may intimate her through contact page of this website to know her so that it will be useful for providing them as early as possible. You can also share your own study materials and it can be published in this website after verification and reviewing. Thank you!