Divide and Conquer Strategy and Recurrence Relations in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the midpoint for dividing the array.

DSA Rust

let mid = (low [1] high) / 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 incorrectly

The midpoint is found by adding low and high indices and dividing by 2.

2fill in blank

medium

Complete the code to recursively call the function on the left half.

DSA Rust

divide_and_conquer(arr, low, [1]);

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

Amid

Bmid - 1

Cmid + 1

Dhigh

Attempts:

3 left

💡 Hint

Common Mistakes

Using mid + 1 for left half

Using high instead of mid

Left half ends at mid - 1 index.

3fill in blank

hard

Fix the error in the base case condition to stop recursion.

DSA Rust

if low [1] high { return; }

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

A>

B<

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using less than or equal instead of greater than

Using equality check incorrectly

Recursion stops when low is greater than high, meaning no elements to process.

4fill in blank

hard

Fill both blanks to complete the recurrence relation for merge sort.

DSA Rust

T(n) = 2T(n [1] 2) + [2]n

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

A/

B*

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication instead of division

Adding instead of subtracting in the argument

The recurrence relation divides n by 2 and adds linear time for merging.

5fill in blank

hard

Fill all three blanks to complete the master theorem case for T(n) = aT(n/b) + f(n).

DSA Rust

If f(n) = Θ(n^[1]), and log_b(a) = [2], then:<br> - If [3] > log_b(a), T(n) = Θ(f(n))

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

Ac

Bn

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing n with c

Using less than instead of greater than in comparison

Master theorem compares f(n) growth rate c with log base b of a to determine T(n).

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)