Algorithm Design Techniques : MCQs & PYQs with Explanation

Option D

A Divide and Conquer algorithm are a problem-solving technique where a big problem is broken into smaller ones, solved individually, and then combined to produce the final answer. This method is used in algorithms like Merge Sort, Quick Sort, and Binary Search. The Divide and Conquer approach follow three main steps:

• Divide: Break the original problem into smaller subproblems.
• Conquer: Solve each subproblem either directly if small enough or by applying recursion.
• Combine: Merge subproblem solutions to solve the original problem.

Option A

Memorization is a key technique used in dynamic programming to improve efficiency by:

• Saving the results of expensive function calls.
• Reusing those saved results when the same sub-problem occurs again.

In  other word, instead of recalculating the result every time, we "memorize" (store) it — typically using an array, map, or hash table.
 

Option A

In Genetic Algorithms (GA), encoding represents a possible solution in the form of a Chromosome. Different problems require different encoding methods depending on the structure of the solution.
Binary Encoding : Knapsack Problem
Binary encoding uses 0 and 1. In the Knapsack Problem, 1 can represent selecting an item and 0 can represent not selecting it.
Permutation Encoding : T.S.P. Scheduling
Permutation encoding represents a solution as an ordered sequence. It is suitable for TSP (Travelling Salesman Problem) because the order in which cities are visited is important.
Value Encoding : Generic Programming
Value encoding represents solutions using actual values, such as numbers or other problem-specific values. It is suitable for generic programming applications.
Tree Encoding : Engineering Design
Tree encoding represents a solution using a tree structure, making it suitable for problems involving hierarchical or structural designs, such as engineering design.

Option D

The Greedy Strategy solves a problem by making the best possible choice at each step, with the expectation that these locally optimal choices will lead to a globally optimal solution.

Bellman-Ford Algorithm is based on the Dynamic Programming approach, specifically repeated edge relaxation, rather than the Greedy strategy.
The actual use of Huffman Coding is data compression (Lossless Compression) (ZIP, JPEG, PNG). It reduces the number of bits required to represent data, especially when some characters/symbols occur much more frequently than others.
The two important greedy algorithms used for Minimum Spanning Tree are Kruskal's Algorithm and Prim's Algorithm.

• Kruskal Algorithm selects the minimum-weight edge from the available edges, avoiding cycles.
• Prim Algorithm starts from a vertex and repeatedly selects the minimum-weight edge that connects the growing tree to a new vertex.

Option B

A Greedy Algorithm is a problem-solving technique in which the algorithm makes the best possible choice at the current step, without considering future consequences.
The main idea is to select the locally optimal solution at each stage with the hope that these choices will lead to a globally optimal solution.
Instead of exploring all possible solutions, the greedy approach selects the best immediate option according to a specific criterion such as minimum cost, maximum profit, or shortest distance.
This behavior distinguishes greedy algorithms from Dynamic Programming and Backtracking.

• Dynamic Programming examines overlapping subproblems and stores results to ensure the global optimum.
• Backtracking or Exhaustive Search checks all possible solutions before selecting the best one.

Option C

The Divide and Conquer Approach solves problems by dividing them into smaller independent subproblems and combining their solutions, which is exactly how Strassen Matrix Multiplication reduces matrix multiplication complexity.
Strassen’s Algorithm divides matrices into smaller sub-matrices, solves them recursively, and then combines the results.
Dynamic Programming is used when a problem has overlapping subproblems and optimal substructure. Dynamic programming stores intermediate results to avoid repeated computation. The 0/1 Knapsack problem has overlapping subproblems and optimal substructure.
The Greedy Approach works by making locally optimal choices, and Huffman Encoding uses this idea by repeatedly choosing the least frequent symbols to build an optimal coding tree.
The Backtracking is used to explore all possible solutions by trying choices and undoing them if they lead to failure. Graph Coloring tries different color assignments and backtracks whenever a conflict occurs, making backtracking the suitable approach.

Option D

The 0/1 Knapsack problem is a classic combinatorial optimization problem where each item must be either included or excluded from the knapsack. In this version, the objective is to minimize the profit (or cost), rather than maximize it. Simple greedy methods are not suitable here because they do not always guarantee an optimal solution for 0/1 decisions.

To handle minimization effectively, the Branch & Bound (0/1) technique is used. This method systematically explores all possible combinations of items while using bounds to prune suboptimal branches, which reduces unnecessary computations. While dynamic programming or backtracking can also solve the problem.