M.C.A. DEGREE EXAMINATION, APRIL 2016
Second Semester
DESIGN AND ANALYSIS OF ALGORITHMS
(Common for M.C.A. WEP)
(2012 onwards)
Time 3 Hours Maximum 75 Marks
Part A (10 2 20)
Answer all questions.
All questions carry equal marks.
1. Define algorithm.
2. What is space complexity?
3. Define sequential search.
4. What is Greedy technique?
5. How to find the "degree of tree"?
6. What is the purpose of Dijkstra's algorithm?
7. Define breadth first search.
8. Define heap sort.
Sub. Code
541203/
545203
RW-10779
2
sp3
9. What is Hamilton's circuit? Give an example.
10. Define NP complete problem.
Part B 5 25)
Answer all questions, choosing either or
All questions carry equal marks.
11. What are the important problem types? Explain
them briefly.
Or
Describe the desirable characteristic of an
algorithm.
12. Explain the Mathematical analysis of recursive
algorithm.
Or
Describe the Quick sort procedure with an example.
13. Discuss the steps in developing a Dynamic
programming algorithm. Illustrate with an
example.
Or
Describe the Prim's algorithm.
14. Explain the insertion sort with suitable example.
Or
Describe the reduction of optimization problem.
RW-10779
3
sp3
15. Apply the Branch and Bound algorithm to solve the
travelling salesman problem
Or
Discuss about the NP complete problem.
Part C 10 30)
Answer any three questions.
All questions carry equal marks.
16. Explain Big Oh Notation, Omega Notation and Theta
Notations. Give an examples.
17. Explain the Strassen's multiplication algorithm with
suitable example.
18. Describe the Dijikstra's algorithm with suitable example.
19. Explain the concept of Heap sort with suitable example.
20. Explain the eight Queen's problem with an example.