CS Free MCQ Bank

[ 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 C ]

Spatial Locality is a principle of memory access that states if a memory location is accessed, nearby memory locations are likely to be accessed soon. Since arrays store data in contiguous memory locations, accessing elements sequentially benefits heavily from spatial locality. Thus, arrays highly utilize this concept.

[ 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 D ]

A data structure is indeed a particular way of organizing and storing data so that it can be accessed and modified efficiently. This is true.
Subtraction of two pointers gives the difference in terms of number of elements (blocks) between them, not bytes. This is true.
A function is a block of statements used to perform a specific task. This is true.
Since all the given statements (A), (B), and (C) are true, there is no false statement among them.

[ Option C ]

NP-Complete problems are a class of computational problems that are considered difficult because, while a proposed solution can be verified quickly (in polynomial time), there is no known algorithm that can solve all instances of the problem efficiently. Examples include the Traveling Salesman Problem (TSP), which involves finding the shortest possible route visiting all cities, and the Boolean Satisfiability Problem (SAT), which asks whether a boolean formula can be satisfied.
The Shortest Path Problem, which finds the minimum path between nodes in a graph, is not NP-Complete, because it can be solved efficiently in polynomial time using algorithms like Dijkstra’s or Bellman-Ford.

[ 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.