DAA Unit 4: Advanced Design and Analysis Previous Year Questions

by
  1. Write a note on Dynamic programming.
  2. Write a difference between Dynamic programming and Greedy approach.
  3. Write the elements of Dynamic programming.
  4. Explain Matrix-chain multiplication problem and solve it by using Dynamic Programming with one example.
  5. Explain Longest Common Subsequence. Write its pseudo code for computing the length of LCS.
  6. Explain knapsack problem. Write its Greedy Solution.
  7. Explain knapsack problem. Write Dynamic Programming Solution for 0/1 knapscak problem.
  8. What is optimization problem? How are greedy method can be used to solve the optimization problem?
  9. Explain dynamic programming method. Formulate dynamic programming recurrence equation for 0/1 knapsack problem.
  10. Describe All-Pair Shortest Path problem and discuss O(n^3) algorithm to solve it.
  11. Discuss the Floyd-Warshall algorithm.
  12. What do you mean by Backtracking? Explain.
  13. Explain the Hamiltonian circuit problem with an example.
  14. Discuss the N-Queen Problem.
  15. Explain the Subset-Sum Problem..
  16. Describe travelling salesman problem(TSP). Show that a TSP can be solved using backtracking method in the exponential time.
  17. What do you mean by “Greedy Algorithm”? Write its pseudo code and prove that the fractional knapsack problem has a greedy-choice property.
  18. Write the difference between Backtracking and Branch and Bound approach.
  19. Write Branch and Bound algorithm for Knapsack problem.
  20. Write Branch and Bound algorithm for Travelling salesman problem.
  21. What do you mean by graph coloring and graph coloring problem? What do you mean by optimal coloring of a graph? Show that every bipartite graph is 2-colorable.