Anna University, Chennai
Department of Computer Science Engineering
4th Semester
CS2251 Design and Analysis of Algorithms
Most Important Questions - 2014 Edition
(Regulation 2008)
UNIT I
1. Explain Towers of Hanoi problem and solve it using recursion.
2. Find the time complexity and space complexity of the following problems.
3. Factorial using Recursion.
4. Compute nth Fibonacci Number.
5. Compute xn or exponentiate (x,n).
6. mxn matrix multiplication , mxn matrix addition.
7 Sequential/linear search.
8. Describe best, worst and average case analysis with an example.
UNIT II
1. Explain the binary search algorithm with an example.
2. Explain mimmax problem using Divide and conquer technique. Compute its time complexity.
3. Explain merge sort with an example. Compute its time complexity.
4. Explain Quick sort with an example. Give its time complexity.
5. Solve the knapsack problem using greedy technique.
6. Explain Prim’s algorithm to construct Minimum cost spanning tree.
7. Explain Kruskal’s algorithm to construct Minimum cost spanning tree.
8. Explain Optimal Randomized algorithm to construct Minimum cost spanning tree.
9. Explain single source shortest path algorithm (Dijkstra’s algorithm).
UNIT III
1. Explain all pairs shortest path algorithm with an eg. Give its time complexity
2. What is multistage graph? Explain with an eg. Write the pseudo code for the finding the minimum cost path using forward approach.
3. What is multistage graph? Explain with an eg. Write the pseudo code for the finding the minimum cost path using backward approach.
4. Write an algorithm for 0/1 knapsack problem.
5. Write and explain an algorithm for BFS and DFS. Give an eg.
6. Give an algorithm to identify articulation points and to construct biconnected components.Explain with an eg.
UNIT IV
1. Explain N-Queens problem using Backtracking.
2. Explain Graph Coloring.
3. Explain sum of subsets.
4. Explain Hamiltonian cycles.
5. Solve Knapsack problem using backtracking.
6. Explain Traveling Salesperson problem using branch and bound techniques.
UNIT V
1. Explain the basic concepts of P, NP, NP-Complete and NP-Hard.
2. Prove a graph problem is NP-Hard.
3. Explain a NP-Hard Scheduling problem.
4. Explain a NP-Hard code generation problem.
5. Explain the concepts of Approximation algorithm.
