Divide and Conquer Strategy and Recurrence Relations in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Merge Sort Call Count

Consider the following Rust function that counts the number of recursive calls made during a merge sort on an array of size n. What is the output when calling count_merge_sort_calls(8)?

DSA Rust

fn count_merge_sort_calls(n: usize) -> usize {
    if n <= 1 {
        1
    } else {
        1 + count_merge_sort_calls(n / 2) + count_merge_sort_calls(n - n / 2)
    }
}

fn main() {
    println!("{}", count_merge_sort_calls(8));
}

A 8

B 16

C 15

D 7

💡 Hint

Think about how many times the function splits the array and counts calls recursively.

The function counts 1 for the current call plus the calls for the left and right halves. For n=8, the total calls sum to 15.

🧠 Conceptual

intermediate

Master Theorem Case Identification

Given the recurrence relation T(n) = 3T(n/4) + n, which case of the Master Theorem applies and what is the asymptotic complexity?

A Case 1: T(n) = Θ(n^{log_4 3})

B Case 2: T(n) = Θ(n log n)

C Case 1: T(n) = Θ(n^{log_3 4})

D Case 3: T(n) = Θ(n)

💡 Hint

Compare f(n) = n with n^{log_b a} where a=3 and b=4.

log_4 3 ≈ 0.792, and since f(n) = n = n^{1} which is asymptotically larger than n^{0.792}, this fits Case 3 where f(n) is larger, so T(n) = Θ(n).

🔧 Debug

advanced

Identify the Error in Recursive Fibonacci Implementation

What error will the following Rust code produce when calling fib(5)?

DSA Rust

fn fib(n: i32) -> i32 {
    if n == 0 {
        0
    } else if n == 1 {
        1
    } else {
        fib(n - 1) + fib(n - 2)
    }
}

fn main() {
    println!("{}", fib(5));
}

A Outputs 5 correctly

B Stack overflow due to infinite recursion

C Compilation error: missing return type

D Runtime panic: integer overflow

💡 Hint

Trace the recursive calls for fib(5).

The code correctly implements Fibonacci recursively and returns 5 for fib(5). No errors occur.

❓ Predict Output

advanced

Output of QuickSort Partition Count

What is the output of the following Rust code that counts the number of partitions performed during QuickSort on the array [3, 6, 2, 7, 5]?

DSA Rust

fn quicksort_partition_count(arr: &mut [i32]) -> usize {
    if arr.len() <= 1 {
        0
    } else {
        let pivot = arr[arr.len() - 1];
        let mut i = 0;
        for j in 0..arr.len() - 1 {
            if arr[j] < pivot {
                arr.swap(i, j);
                i += 1;
            }
        }
        arr.swap(i, arr.len() - 1);
        1 + quicksort_partition_count(&mut arr[0..i]) + quicksort_partition_count(&mut arr[i + 1..arr.len()])
    }
}

fn main() {
    let mut data = [3, 6, 2, 7, 5];
    println!("{}", quicksort_partition_count(&mut data));
}

A 4

B 3

C 5

D 2

💡 Hint

Count how many times the partition step is called recursively.

The partition function is called once per subarray split. For this input, it is called 3 times in total.

🧠 Conceptual

expert

Recurrence Relation for Strassen's Matrix Multiplication

Strassen's algorithm for multiplying two n×n matrices uses 7 recursive multiplications of size n/2 and additional work proportional to n^2. Which recurrence relation correctly models its time complexity?

A T(n) = 7T(n/2) + Θ(n^2)

B T(n) = 8T(n/2) + Θ(n^3)

C T(n) = 6T(n/3) + Θ(n^2)

D T(n) = 7T(n/2) + Θ(n^3)

💡 Hint

Recall how many recursive multiplications and the cost of combining results in Strassen's algorithm.

Strassen's algorithm reduces the number of multiplications to 7 on subproblems of size n/2, with additional linear work in n^2 for additions and subtractions.

Practice

1. What is the main idea behind the Divide and Conquer strategy in algorithms?

easy

A. Break the problem into smaller subproblems, solve them independently, then combine results

B. Solve the problem by trying all possible solutions one by one

C. Use a single loop to iterate through all elements

D. Store all intermediate results to avoid repeated calculations

Solution

1. Step 1: Understand the divide and conquer approach

   It splits a big problem into smaller parts that are easier to solve.

2. Step 2: Combine the solutions of subproblems

   After solving smaller parts, their results are merged to get the final answer.

3. Final Answer:

   Break the problem into smaller subproblems, solve them independently, then combine results -> Option A

4. Quick Check:

   Divide and conquer = split, solve, combine [OK]

Hint: Divide big problem into smaller parts, solve, then merge [OK]

Common Mistakes:

• Confusing divide and conquer with brute force
• Thinking it uses only one loop
• Mixing with dynamic programming concepts

2. Which of the following is the correct Rust syntax to define a recursive function for the divide and conquer approach?

easy

A. fn divide_and_conquer(n: i32) -> i32 { if n == 0 { 0 } else { n * divide_and_conquer(n) } }

B. fn divide_and_conquer(n: i32) { while n > 1 { n -= 1; } }

C. fn divide_and_conquer(n: i32) -> i32 { loop { return n; } }

D. fn divide_and_conquer(n: i32) -> i32 { if n == 1 { 1 } else { divide_and_conquer(n - 1) + 1 } }

Solution

1. Step 1: Check for base case in recursion

   fn divide_and_conquer(n: i32) -> i32 { if n == 1 { 1 } else { divide_and_conquer(n - 1) + 1 } } has a base case: if n == 1 returns 1, which stops recursion.

2. Step 2: Verify recursive call reduces problem size

   fn divide_and_conquer(n: i32) -> i32 { if n == 1 { 1 } else { divide_and_conquer(n - 1) + 1 } } calls divide_and_conquer(n - 1), reducing n each time.

3. Final Answer:

   fn divide_and_conquer(n: i32) -> i32 { if n == 1 { 1 } else { divide_and_conquer(n - 1) + 1 } } -> Option D

4. Quick Check:

   Recursive function needs base case and smaller input [OK]

Hint: Look for base case and smaller recursive call [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Not reducing input in recursive call
• Using loops instead of recursion

3. Consider the following Rust function implementing merge sort. What will be the output when calling merge_sort(vec![3, 1, 4, 2])?

fn merge_sort(mut arr: Vec<i32>) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr;
    }
    let mid = arr.len() / 2;
    let left = merge_sort(arr.drain(..mid).collect());
    let right = merge_sort(arr);
    merge(left, right)
}

fn merge(left: Vec<i32>, right: Vec<i32>) -> Vec<i32> {
    let mut result = Vec::new();
    let mut i = 0;
    let mut j = 0;
    while i < left.len() && j < right.len() {
        if left[i] < right[j] {
            result.push(left[i]);
            i += 1;
        } else {
            result.push(right[j]);
            j += 1;
        }
    }
    result.extend_from_slice(&left[i..]);
    result.extend_from_slice(&right[j..]);
    result
}

medium

A. [3, 1, 4, 2]

B. [4, 3, 2, 1]

C. [1, 2, 3, 4]

D. [1, 3, 2, 4]

Solution

1. Step 1: Understand merge sort splits and sorts

   The function splits the array into halves recursively until size 1, then merges sorted halves.

2. Step 2: Trace sorting of input [3, 1, 4, 2]

   Splitting: [3,1] and [4,2], then [3], [1], [4], [2]. Merging sorted pairs: [1,3] and [2,4]. Final merge: [1,2,3,4].

3. Final Answer:

   [1, 2, 3, 4] -> Option C

4. Quick Check:

   Merge sort output is sorted array ascending [OK]

Hint: Merge sort always returns sorted array ascending [OK]

Common Mistakes:

• Confusing merge order causing reversed output
• Not understanding recursive splitting
• Ignoring that merge combines sorted halves

4. The following Rust function is intended to compute the Fibonacci number using divide and conquer. Identify the bug:

fn fib(n: u32) -> u32 {
    if n <= 1 {
        return n;
    }
    fib(n - 1) + fib(n - 1)
}

medium

A. It misses the base case for n == 0

B. It calls fib(n - 1) twice instead of fib(n - 1) and fib(n - 2)

C. It uses u32 instead of i32 for n

D. It should use a loop instead of recursion

Solution

1. Step 1: Check recursive calls in function

   The function calls fib(n - 1) twice, which is incorrect for Fibonacci.

2. Step 2: Recall Fibonacci formula

   Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2), so one call should be fib(n - 2).

3. Final Answer:

   It calls fib(n - 1) twice instead of fib(n - 1) and fib(n - 2) -> Option B

4. Quick Check:

   Fibonacci needs fib(n-1) + fib(n-2) [OK]

Hint: Fibonacci sums fib(n-1) and fib(n-2) [OK]

Common Mistakes:

• Calling fib(n-1) twice causing wrong results
• Ignoring base cases
• Confusing parameter types

5. Given the recurrence relation T(n) = 2T(n/2) + n, which of the following is the correct time complexity using the Master Theorem?

hard

A. O(n log n)

B. O(n^2)

C. O(log n)

D. O(n)

Solution

1. Step 1: Identify parameters a, b, and f(n)

   Here, a = 2, b = 2, and f(n) = n.

2. Step 2: Calculate log_b(a)

   log_2(2) = 1.

3. Step 3: Compare f(n) with n^{log_b(a)}

   f(n) = n and n^{log_b(a)} = n^1 = n, so f(n) = Theta(n^{log_b(a)}).

4. Step 4: Apply Master Theorem case 2

   When f(n) = Theta(n^{log_b(a)}), T(n) = Theta(n log n).

5. Final Answer:

   O(n log n) -> Option A

6. Quick Check:

   Master theorem case 2 gives O(n log n) [OK]

Hint: Use Master Theorem: compare f(n) to n^{log_b(a)} [OK]

Common Mistakes:

• Confusing log base or parameters a and b
• Choosing wrong Master Theorem case
• Ignoring the additive term f(n)