Reg. No.
B.E. B.Tech. DEGREE EXAMINATION, MAY 2017
Fourth Semester
Computer Science and Engineering
01UCS404 DESIGN AND ANALYSIS OF ALGORITHMS
(Regulation 2013)
Duration: Three hours Maximum: 100 Marks
Answer ALL Questions.
PART A (10 x 2 20 Marks)
1. Analyze the steps involved in the analysis framework?
2. Differentiate recursive and non-recursive algorithms.
3. List the strength and weakness of brute force algorithm.
4. What is knapsack problem?
5. How do you obtain a solution to an optimization problem using greedy technique?
6. State the uses of memory functions to solve knapsack problem.
7. Show the Mathematical formulation to solve a max flow problem.
8. Summarizethe steps to print all edges of minimum cut.
9. Define NP Hard and NP Completeness.
10. Draw a graph with cycle but with no Hamiltonian cycle.
Question Paper Code: 31224
2
31224
PART B x 16 80 Marks)
11. Briefly explain the steps in mathematical analysis of recursive algorithms.
Or
Write the recursive and non-recursive versions of Fibonacci series function. Examine how much time each function requires as becomes large.
12. Write an algorithm for Quicksort and sort the list 7. Also find its time complexity.
Or
Explain the binary search algorithm with best, average and worst case time complexities.
13. What is optimal binary search tree? Write the algorithm to find the optimal binary search tree by dynamic programming.
Or
Write the Floyd's algorithm for solving all pair shortest path.
14. Briefly explain the stable marriage problem. Find the best and worst case time complexity.
Or
What is maximum matching? Illustrate the steps involved in finding the maximum matching in Bipartite Graphs.
15. Explain in detail about assignment problem.
Or
Explain NP hard and NP complete problems with example.