M.C.A.(R)/M.C.A. DEGREE EXAMINATION,
APRIL 2017
Second Semester
DESIGN AND ANALYSIS OF ALGORITHMS
(2012 onwards)
Time 3 Hours Maximum 75 Marks
Part A (10 X 2 20)
Answer all questions.
1. Define the term algorithm.
2. What is space complexity?
3. Give two example of divide and conquer algorithm.
4. What is a sequential search?
5. Define Greedy technique.
6. How to find the "degree of tree"?
7. What is the purpose of Dijkstra's algorithm?
8. Write note heap sort.
9. What is a Hamilton's circuit? Give an example.
10. Define NP complete problem.
Sub. Code
541203/
545203
RW-155
2
Wk 10
Part B X 5 25)
Answer all questions choosing either or
11. Write a recursive algorithm to compute a factorial of
positive integer and analysis a time complexity.
Or
Explain the desirable characteristic of an algorithm.
12. Explain about the Quick sort with detail example.
Or
Describe about the 0/1 knapsack problem.
13. Discuss about the optimal binary search tree with
example.
Or
Discuss the step in developing a Dynamic
programming Algorithm. Illustrate with example.
14. Describe about insertion sort with suitable example.
Or
Write short note on reduction of optimization
problem.
15. Discuss about the NP hard problem.
8
RW-155
3
Wk 10
Part C X 10 30)
Answer any three questions.
16. Explain briefly Big Oh Notation, Omega Notation and
Theta Notations. Give an examples.
17. Write the merge sort algorithm to sort the following
numbers 12, 14, 25, 27, 11, 12, 13, 16. Illustrate the
algorithm.
18. Explain briefly about the 8 Queen's problem with
example.
19. Explain about the concept of Backtracking and Branch
and bound technique with suitable example.
20. Explain in detail about an approximation algorithm and
how they can be used for NP hard problem.
—————