DP vs Recursion vs Greedy Choosing the Right Tool in DSA C# - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate Fibonacci number using recursion.

DSA C#

int Fibonacci(int n) {
    if (n <= 1) return n;
    return Fibonacci(n - 1) [1] Fibonacci(n - 2);
}

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition.

Using multiplication or division which changes the sequence.

The Fibonacci sequence is calculated by adding the two previous numbers.

2fill in blank

medium

Complete the code to implement memoization for Fibonacci to avoid repeated calculations.

DSA C#

int FibonacciMemo(int n, Dictionary<int, int> memo) {
    if (n <= 1) return n;
    if (memo.ContainsKey(n)) return memo[n];
    memo[n] = FibonacciMemo(n - 1, memo) [1] FibonacciMemo(n - 2, memo);
    return memo[n];
}

Drag options to blanks, or click blank then click option'

A/

B-

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Not storing the result in the memo dictionary.

Memoization stores results of Fibonacci sums to avoid recalculations.

3fill in blank

hard

Fix the error in the greedy approach to select the maximum number of activities that don't overlap.

DSA C#

List<Activity> SelectActivities(List<Activity> activities) {
    activities.Sort((a, b) => a.EndTime [1] b.EndTime);
    List<Activity> selected = new List<Activity>();
    int lastEnd = 0;
    foreach (var activity in activities) {
        if (activity.StartTime >= lastEnd) {
            selected.Add(activity);
            lastEnd = activity.EndTime;
        }
    }
    return selected;
}

Drag options to blanks, or click blank then click option'

A>

B+

C-

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or comparison operators instead of subtraction in Sort.

Sorting by start time instead of end time.

Sorting activities by their end time ascending uses subtraction (a.EndTime - b.EndTime) for correct order.

4fill in blank

hard

Fill both blanks to implement bottom-up dynamic programming for the coin change problem.

DSA C#

int CoinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    for (int i = 1; i <= amount; i++) {
        dp[i] = amount + 1;
        for (int j = 0; j < coins.Length; j++) {
            if (coins[j] <= i) {
                dp[i] = Math.Min(dp[i], dp[i [1] coins[j]] [2] 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction for indexing dp.

Not adding 1 to count the current coin.

We subtract coin value from i to get previous state and add 1 coin to count.

5fill in blank

hard

Fill all three blanks to implement recursive solution with memoization for the knapsack problem.

DSA C#

int Knapsack(int[] weights, int[] values, int capacity, int index, Dictionary<(int, int), int> memo) {
    if (index == weights.Length || capacity == 0) return 0;
    if (memo.ContainsKey((index, capacity))) return memo[(index, capacity)];
    int skip = Knapsack(weights, values, capacity, index [1] 1, memo);
    int take = 0;
    if (weights[index] <= capacity) {
        take = values[index] + Knapsack(weights, values, capacity [2] weights[index], index [3] 1, memo);
    }
    memo[(index, capacity)] = Math.Max(skip, take);
    return memo[(index, capacity)];
}

Drag options to blanks, or click blank then click option'

A+

B-

C++

D--

Attempts:

3 left

💡 Hint

Common Mistakes

Using decrement operators instead of addition for index.

Adding weight to capacity instead of subtracting.

We move to next index by adding 1, and reduce capacity by subtracting weight.

Practice

1. Which approach is best suited when a problem has overlapping subproblems and optimal substructure?

easy

A. Simple Recursion

B. Dynamic Programming

C. Greedy Algorithm

D. Brute Force

Solution

1. Step 1: Understand problem characteristics

   Overlapping subproblems mean the same smaller problems repeat. Optimal substructure means the best solution can be built from best solutions of smaller problems.

2. Step 2: Match approach to characteristics

   Dynamic Programming stores results of subproblems to avoid recomputation, ideal for overlapping subproblems and optimal substructure.

3. Final Answer:

   Dynamic Programming -> Option B

4. Quick Check:

   Overlapping subproblems + optimal substructure = Dynamic Programming [OK]

Hint: Use DP when subproblems repeat and build optimal solutions [OK]

Common Mistakes:

• Choosing greedy when subproblems overlap
• Using simple recursion without memoization
• Confusing optimal substructure with greedy choice

2. Which of the following C# code snippets correctly implements a greedy approach to find the maximum number of activities that don't overlap given start and end times arrays (assuming sorted by end time)?

easy

A. int count = 1; int lastEnd = end[0]; for (int i = 1; i < start.Length; i++) { if (start[i] >= lastEnd) { count++; lastEnd = end[i]; } } Console.WriteLine(count);

B. int count = 0; for (int i = 0; i < start.Length; i++) { if (start[i] > end[i]) count++; } Console.WriteLine(count);

C. int count = 1; for (int i = 1; i < start.Length; i++) { if (end[i] >= start[i-1]) count++; } Console.WriteLine(count);

D. int count = 0; foreach (var s in start) { count += s; } Console.WriteLine(count);

Solution

1. Step 1: Understand greedy activity selection logic

   We select the first activity, then pick next activities starting after the last selected activity ends.

2. Step 2: Check code correctness

   int count = 1; int lastEnd = end[0]; for (int i = 1; i < start.Length; i++) { if (start[i] >= lastEnd) { count++; lastEnd = end[i]; } } Console.WriteLine(count); initializes count to 1, tracks lastEnd, and increments count only if start[i] >= lastEnd, updating lastEnd. This matches greedy logic.

3. Final Answer:

   the code that tracks lastEnd -> Option A

4. Quick Check:

   Greedy activity selection code = int count = 1; int lastEnd = end[0]; for (int i = 1; i < start.Length; i++) { if (start[i] >= lastEnd) { count++; lastEnd = end[i]; } } Console.WriteLine(count); [OK]

Hint: Pick next activity starting after last selected ends [OK]

Common Mistakes:

• Not sorting activities by end time before selection
• Comparing start[i] with wrong end time
• Counting activities incorrectly

3. What is the output of the following C# code that uses recursion to calculate Fibonacci numbers without memoization?

int Fib(int n) { if (n <= 1) return n; return Fib(n - 1) + Fib(n - 2); } Console.WriteLine(Fib(5));

medium

A. 3

B. 8

C. 5

D. 13

Solution

1. Step 1: Trace recursive calls for Fib(5)

   Fib(5) = Fib(4) + Fib(3); Fib(4) = Fib(3) + Fib(2); Fib(3) = Fib(2) + Fib(1); Fib(2) = Fib(1) + Fib(0); Fib(1)=1, Fib(0)=0.

2. Step 2: Calculate values bottom-up

   Fib(0)=0, Fib(1)=1, Fib(2)=1, Fib(3)=2, Fib(4)=3, Fib(5)=5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Fibonacci(5) = 5 by definition [OK]

Common Mistakes:

• Confusing index starting at 0 or 1
• Miscomputing recursive sums
• Assuming memoization changes output

4. The following C# code attempts to solve the coin change problem using recursion but has a bug. What is the bug?

int CoinChange(int[] coins, int amount) { if (amount == 0) return 0; if (amount < 0) return -1; int min = int.MaxValue; foreach (int coin in coins) { int res = CoinChange(coins, amount - coin); if (res >= 0 && res < min) min = 1 + res; } return min == int.MaxValue ? -1 : min; }

medium

A. No memoization causing repeated calculations

B. Incorrect base case for amount == 0

C. Returning -1 instead of 0 for amount < 0

D. Using foreach instead of for loop

Solution

1. Step 1: Analyze recursion and base cases

   Base cases are correct: 0 returns 0, negative returns -1. The recursion tries all coins.

2. Step 2: Identify missing optimization

   Without memoization, the function recalculates subproblems many times, causing inefficiency and possible stack overflow.

3. Final Answer:

   No memoization causing repeated calculations -> Option A

4. Quick Check:

   Missing memoization = No memoization causing repeated calculations [OK]

Hint: Add memo dictionary to avoid repeated calls [OK]

Common Mistakes:

• Thinking base cases are wrong
• Believing loop type causes bug
• Ignoring performance issues

5. You want to find the minimum number of coins needed to make a given amount using coins of different denominations. Which approach is best and why?

hard

A. Greedy algorithm may fail for some coin sets

B. Simple iteration misses subproblem reuse

C. Recursion without memoization is inefficient

D. Dynamic programming ensures optimal solution efficiently

Solution

1. Step 1: Evaluate greedy approach limitations

   Greedy works only if coin denominations are canonical (like US coins). Otherwise, it can fail to find minimum coins.

2. Step 2: Consider recursion and iteration drawbacks

   Recursion without memoization repeats work; simple iteration without storing results misses subproblem reuse.

3. Step 3: Understand dynamic programming benefits

   DP with bottom-up tabulation stores minimum coins for all amounts up to target, guaranteeing optimal and efficient solution.

4. Final Answer:

   Dynamic programming ensures optimal solution efficiently -> Option D

5. Quick Check:

   Minimum coins problem = DP bottom-up [OK]

Hint: Use DP tabulation for guaranteed minimum coins [OK]

Common Mistakes:

• Assuming greedy always works
• Ignoring performance of recursion
• Not storing intermediate results