Dynamic Programming MCQs

The binomial coefficient C(n, k) can be computed using:

a) Divide and Conquer b) Dynamic Programming c) Greedy Method d) Backtracking

Correct Answer: b) Dynamic Programming

Explanation:
The binomial coefficient has overlapping subproblems and optimal substructure, making it suitable for dynamic programming. While other methods could compute it, DP provides the most efficient solution with O(nk) time complexity.

The recurrence relation for C(n, k) is:

a) C(n-1, k-1) + C(n-1, k) b) C(n-1, k) + C(n, k-1) c) C(n, k-1) + C(n-1, k) d) C(n-1, k-1) + C(n, k-1)

Correct Answer: a) C(n-1, k-1) + C(n-1, k)

Explanation:
This is Pascal's identity which forms the basis of the DP solution. It states that any element in Pascal's triangle is the sum of the two elements directly above it (one from the same column and one from the previous column).

The time complexity of computing C(n, k) using DP is:

a) O(n) b) O(n log n) c) O(nk) d) O(2ⁿ)

Correct Answer: c) O(nk)

Explanation:
The DP solution fills a 2D table of size n×k, with each cell taking constant time to compute. This results in O(nk) time complexity. The space complexity can be optimized to O(k).

Warshall's algorithm is used to find:

a) Shortest paths in a weighted graph b) Transitive closure of a graph c) Minimum Spanning Tree d) Maximum flow

Correct Answer: b) Transitive closure of a graph

Explanation:
Warshall's algorithm computes the transitive closure of a directed graph, determining if there is a path between all pairs of vertices. It's a DP approach that builds the solution incrementally by considering intermediate vertices.

Floyd-Warshall algorithm computes:

a) Single-source shortest paths b) All-pairs shortest paths c) Strongly connected components d) Eulerian path

Correct Answer: b) All-pairs shortest paths

Explanation:
Floyd-Warshall is a DP algorithm that finds shortest paths between all pairs of vertices in a weighted graph. It handles negative weights (but not negative cycles) and is suitable for dense graphs represented as adjacency matrices.

The time complexity of Floyd-Warshall is:

a) O(V²) b) O(V³) c) O(E log V) d) O(V log V)

Correct Answer: b) O(V³)

Explanation:
The algorithm uses three nested loops over all vertices, resulting in O(V³) time. The space complexity is O(V²) for storing the distance matrix. It's particularly effective when the graph is dense (E ≈ V²).

The OBST problem minimizes:

a) Tree height b) Total search cost c) Number of leaves d) Rotation operations

Correct Answer: b) Total search cost

Explanation:
OBST minimizes the expected search cost given access frequencies for each key. It considers both successful searches (keys) and unsuccessful searches (between keys), arranging them to minimize the total cost based on their probabilities.

The time complexity of OBST using DP is:

a) O(n) b) O(n²) c) O(n³) d) O(2ⁿ)

Correct Answer: c) O(n³)

Explanation:
The DP solution fills an n×n table where each cell takes O(n) time to compute, resulting in O(n³) total time. The space complexity is O(n²). This is more efficient than the exponential time of a naive recursive solution.

In OBST, keys are stored in:

a) Internal nodes b) Leaf nodes c) Both internal and leaf nodes d) Root only

Correct Answer: a) Internal nodes

Explanation:
In OBST (like in all BSTs), keys are stored in internal nodes. The dummy nodes (representing unsuccessful search intervals) are considered to be in the leaves. This structure allows the algorithm to account for both successful and unsuccessful search probabilities.

The 0/1 Knapsack problem is solved using:

a) Greedy algorithm b) Dynamic Programming c) Backtracking d) Branch and Bound

Correct Answer: b) Dynamic Programming

Explanation:
The 0/1 Knapsack problem has both optimal substructure and overlapping subproblems, making it ideal for DP. While other methods can solve it, DP provides the most efficient pseudo-polynomial solution with O(nW) time complexity, where n is number of items and W is capacity.

The time complexity of 0/1 Knapsack (DP) is:

a) O(n) b) O(n log n) c) O(nW) d) O(2ⁿ)

Correct Answer: c) O(nW)

Explanation:
The DP solution uses a table of size n×W, with each cell taking constant time to fill. This results in O(nW) time complexity. Note that this is pseudo-polynomial because W is numeric value of input, not input size. The space complexity can be optimized to O(W).

Fractional Knapsack is solved using:

a) DP b) Greedy algorithm c) Backtracking d) Divide & Conquer

Correct Answer: b) Greedy algorithm

Explanation:
Fractional Knapsack can be optimally solved by a greedy approach - sorting items by value-to-weight ratio and taking items in that order. This works because we can take fractions of items. The time complexity is O(n log n) due to the sorting step.

Your Score: /12