M.Tech-M.Tech Computer Science 4th Sem DESIGN AND ANALYSIS OF ALGORITHMS (Acharya Nagarjuna University (ANU), Guntur, Andhra Pradesh-2012)
Sunday, 25 August 2013 10:22anudouglas
(Examination at the end of Final Year)
Computer Science
Paper II – DESIGN AND ANALYSIS OF ALGORITHMS
Time : Three hours Maximum : 75 marks
Answer Question No. 1 compulsorily.
Answer ONE question from each Unit.
All questions carry equal marks.
1. (a) Define Big oh notation.
(b) Enumerate some important types of problem.
(c) How will you measure input size of algorithm?
(d) What is the average case complexity of linear search algorithm?
(e) Write the procedure of selection sort.
(f) Define depth first searching technique.
(g) What is AVL Tree?
UNIT I
2. Explain divide and conquer with suitable example. Also discuss its merits.
Or
3. Write an algorithm for finding maximum element of an array. Also perform best, worst
and average case complexity, defining the notations used for each type of analysis.
UNIT II
4. Explain the guedy method with appropriate example.
Or
5. What is principle of optimality? Explain the dynamic programming method.
UNIT III
6. Explain the breadth first search and traversal techniques with suitable example.
Or
7. Explain backtracking method with suitable example. Discuss its advantages.
UNIT IV
8. Explain the Branch and Bound techniques using travelling salesman problem as an
example.
Or
9. Explain about NP-Hard and NP-complete problems with suitable example.
| Earning: ₹ 5.10/- |
