Questions Search

This website covers previous years question papers of various universities and colleges in India. Moreover, the information on admission to various courses from various universities/institutes/colleges are also available. Research paper questions are also updated from time to time. Also the latest teaching faculty plus teachers jobs, Government jobs, Banking Jobs, and other jobs are regularly updated to help jobless candidates. Admit cards of various recruitment of Govt organisation are updated. Search your terms using the sejavascript:void(0)arch box provided.
Are you student / faculty of Vikram University Ujjain? We are collecting old question papers. If you have latest question papers 2016 / 2015 / 2014 years, then contact us through email [email protected] / [email protected] . We will give you money for your question papers you send to us.

TNPSC Group IV 2016 Model Questions AnswersTNPSC Group IV

Anna Univ B.E Civil Engineering Previous Years Question PapersBE Civil Anna Univ

Anna Univ B.E EEE Previous Years Question PapersB.E EEE Anna Univ Questions

Anna Univ B.E Mechanical Engineering Previous Years Question PapersMechanical B.E Questions

Anna Univ B.E CSE Previous Years Question PapersMechanical B.E Questions

Anna Univ B.E ECE Previous Years Question PapersMechanical B.E Questions

VTU Question PapersLatest News

Dharmsinh Desai University Previous Years Question PapersLatest News

NEW: Last 05+ Years Question Papers of CE6451 Fluid Mechanics and Machinery

NEW: ME6502 Heat and Mass Transfer AU Chennai Last 10 Set of Question Papers

NEW: CE2027 Housing Planning and Management 2014 Question Paper

Himachal Pradesh University (HPU) Previous Years Question Papers

ME2027 PPCE All Previous Years Question Papers [NEW]

GNDU Previous Years Question Papers [NEW]

Teachers TGT, PGT, PRT jobs in New Delhi Schools


Follow by Email

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]


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 >.


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]


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.


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]


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

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

No comments:

Post a Comment

Pen down your valuable important comments below