Divide and Conquer Strategy and Recurrence Relations in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Divide and Conquer strategy?

Divide and Conquer means breaking a big problem into smaller parts, solving each part separately, and then combining the results to get the final answer.

beginner

What does a recurrence relation describe in algorithms?

A recurrence relation shows how the time to solve a problem depends on the time to solve smaller parts of the same problem.

intermediate

Example: If a problem of size n is split into two problems of size n/2, and combining results takes O(n), what is the recurrence relation?

T(n) = 2 * T(n/2) + O(n), where T(n) is the time to solve the problem of size n.

intermediate

What is the Master Theorem used for?

The Master Theorem helps solve recurrence relations of divide and conquer algorithms quickly to find their time complexity.

beginner

In Rust, how would you write a simple divide and conquer function to find the maximum in a slice?

fn max_divide_conquer(arr: &[i32]) -> i32 {
    if arr.len() == 1 {
        arr[0]
    } else {
        let mid = arr.len() / 2;
        let left_max = max_divide_conquer(&arr[..mid]);
        let right_max = max_divide_conquer(&arr[mid..]);
        if left_max > right_max { left_max } else { right_max }
    }
}

What are the three main steps in the Divide and Conquer strategy?

A Split, Merge, Sort

B Divide, Solve, Combine

C Divide, Conquer, Repeat

D Split, Solve, Repeat

The three steps are Divide the problem, Solve the smaller problems, and Combine the results.

Which recurrence relation matches binary search?

A T(n) = 2T(n/2) + O(n)

B T(n) = 3T(n/3) + O(n)

C T(n) = T(n/2) + O(1)

D T(n) = T(n-1) + O(1)

Binary search splits the problem in half and does constant work, so T(n) = T(n/2) + O(1).

If T(n) = 3T(n/3) + O(n), what is the time complexity using Master Theorem?

A O(n)

B O(n^2)

C O(n log n)

D O(log n)

Here a=3, b=3, f(n)=O(n). Since f(n) = Theta(n^{log_b a}), time is O(n).

In divide and conquer, what does the 'combine' step usually involve?

A Merging or joining the solutions of smaller parts

B Breaking the problem into smaller parts

C Ignoring smaller problems

D Sorting the input

The combine step merges or joins the results from smaller solved parts to form the final answer.

Which of these is NOT a divide and conquer algorithm?

A Binary Search

B Quick Sort

C Merge Sort

D Linear Search

Linear Search checks elements one by one and does not divide the problem.

Explain how divide and conquer works using a real-life example.

Think about how you might clean a big room by dividing it into smaller sections.

Describe what a recurrence relation is and how it helps analyze divide and conquer algorithms.

It’s like a recipe that tells you how long each step takes based on smaller steps.

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)