Solution

The correct answer is A-I, B-II, C-III, D-IV.

Key Points

• Dynamic programming: This technique is used to solve problems by breaking them into smaller overlapping subproblems. The Floyd Warshall algorithm is an example of dynamic programming applied to find the shortest paths in a graph.
• Greedy: Greedy algorithms work by making locally optimal choices at each step with the hope of finding a global optimum. Huffman coding is an example of a greedy algorithm used for data compression.
• Backtracking: This is a general algorithmic technique for solving problems incrementally by trying partial solutions and then abandoning them if they are not suitable. The Hamiltonian cycle problem is commonly solved using backtracking.
• Branch and bound: This technique is used for solving optimization problems. The Travelling Salesman Problem (TSP) using lower bound is an example that utilizes branch and bound.

Additional Information

• Dynamic programming:
  • It is used in problems like the Knapsack problem, Fibonacci sequence, and matrix chain multiplication.
  • It is based on the principle of optimality, solving subproblems only once and storing their results.
• Greedy algorithms:
  • Examples include Prim's algorithm, Kruskal's algorithm, and Dijkstra's algorithm for graphs.
  • They do not always guarantee an optimal solution but work well for many specific problems.
• Backtracking:
  • It is used in problems like N-Queens, Sudoku solving, and maze solving.
  • Backtracking systematically searches through all possible configurations until the solution is found.
• Branch and bound:
  • It is used to solve combinatorial and optimization problems like the TSP and integer programming.
  • By calculating bounds, it eliminates suboptimal solutions and focuses on promising branches.