Overlapping Subproblems and Optimal Substructure in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci Recursive Calls

What is the output of the following C code that prints Fibonacci numbers using recursion with overlapping subproblems?

DSA C

#include <stdio.h>

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

int main() {
    for (int i = 0; i < 5; i++) {
        printf("%d ", fib(i));
    }
    return 0;
}

A 0 1 1 2 3

B 1 1 2 3 5

C 0 1 2 3 5

D 1 2 3 5 8

💡 Hint

Remember Fibonacci sequence starts with 0 and 1 for fib(0) and fib(1).

The Fibonacci sequence starts with 0 and 1. The recursive function returns fib(0)=0 and fib(1)=1, then sums previous two results. So the first five numbers are 0,1,1,2,3.

🧠 Conceptual

intermediate

Identifying Overlapping Subproblems

Which of the following problems best demonstrates the concept of overlapping subproblems in dynamic programming?

A Sorting an array using quicksort

B Finding the shortest path in a graph using Dijkstra's algorithm

C Calculating factorial of a number using recursion

D Computing Fibonacci numbers using naive recursion

💡 Hint

Overlapping subproblems means the same smaller problem is solved multiple times.

Naive recursive Fibonacci calculation solves the same fib(n) multiple times, showing overlapping subproblems. Factorial and quicksort do not reuse subproblems, and Dijkstra's algorithm is a greedy approach.

🔧 Debug

advanced

Debugging Memoization Implementation

What is the output of this C code with memoization for Fibonacci, and why?

DSA C

#include <stdio.h>

int memo[10] = {0};

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

int main() {
    for (int i = 0; i < 7; i++) {
        printf("%d ", fib(i));
    }
    return 0;
}

A 0 1 1 2 3 5 8

B 0 1 2 3 5 8 13

C 0 1 1 2 3 5 0

D 0 1 1 2 3 5 21

💡 Hint

Memoization stores results to avoid repeated calculations.

Memoization caches fib(n) results. Since fib(6) = fib(5) + fib(4) = 5 + 3 = 8, the output is the first 7 Fibonacci numbers starting from 0.

🚀 Application

advanced

Optimal Substructure in Coin Change Problem

Given unlimited coins of denominations 1, 3, and 4, what is the minimum number of coins needed to make amount 6 using optimal substructure?

A 3

B 2

C 4

D 5

💡 Hint

Try breaking amount 6 into smaller amounts and combine optimal solutions.

Minimum coins for 6 can be found by checking 6-1=5, 6-3=3, 6-4=2. Minimum coins for 5 is 2 (4+1), for 3 is 1 (3), for 2 is 2 (1+1). So min is 1 + min(coins for 5,3,2) = 1 + 1 = 2. The minimum is 2 coins (e.g., 3+3).

🧠 Conceptual

expert

Recognizing Problems Without Optimal Substructure

Which problem does NOT exhibit optimal substructure, meaning its optimal solution cannot be constructed from optimal solutions of subproblems?

A Shortest path in a weighted graph without negative cycles

B Matrix chain multiplication

C Longest simple path in a graph

D Knapsack problem with fractional items

💡 Hint

Optimal substructure means combining optimal subproblem solutions gives global optimum.

Longest simple path problem does not have optimal substructure because subpaths of the longest path are not necessarily longest paths themselves. Others have optimal substructure.