Divide and Conquer Strategy and Recurrence Relations in DSA Rust - Build from Scratch

Divide and Conquer Strategy and Recurrence Relations

📖 Scenario: Imagine you have a large list of numbers and you want to find the maximum number quickly. One way is to split the list into smaller parts, find the maximum in each part, and then combine the results. This is called the divide and conquer strategy.

🎯 Goal: You will write a Rust program that uses divide and conquer to find the maximum number in a list. You will also see how the problem breaks down into smaller parts and how the results combine.

📋 What You'll Learn

Create a vector of integers with exact values

Create a helper function to find the maximum using divide and conquer

Use recursion to split the vector into halves

Combine the results to find the overall maximum

Print the final maximum value

💡 Why This Matters

🌍 Real World

Divide and conquer is used in many algorithms like sorting, searching, and processing large data efficiently by breaking problems into smaller parts.

💼 Career

Understanding divide and conquer helps in writing efficient code for tasks like data analysis, software development, and algorithm design.

1

Create the data vector

Create a vector called numbers with these exact integers: 3, 5, 1, 8, 2, 9, 4

DSA Rust

# Create the vector 'numbers' with the given integers
# Your code here

Hint

Use let numbers = vec![3, 5, 1, 8, 2, 9, 4]; to create the vector.

2

Define the divide and conquer function

Define a function called find_max that takes a slice of i32 called slice and returns an i32. This function will find the maximum number using divide and conquer.

DSA Rust

fn main() {
    let numbers = vec![3, 5, 1, 8, 2, 9, 4];
}

// Define the function 'find_max' here
// Your code here

Hint

Use fn find_max(slice: &[i32]) -> i32 to define the function.

3

Implement divide and conquer logic

Inside the find_max function, write code to: - If the slice length is 1, return the only element. - Otherwise, split the slice into two halves. - Recursively call find_max on each half. - Return the maximum of the two results using std::cmp::max.

DSA Rust

fn main() {
    let numbers = vec![3, 5, 1, 8, 2, 9, 4];
}

fn find_max(slice: &[i32]) -> i32 {
    // Implement divide and conquer logic here
    // Your code here
}

Hint

Use recursion and std::cmp::max to combine results.

4

Print the maximum number

In the main function, call find_max with numbers.as_slice() and print the result using println! with the exact text: "Maximum number is: {}".

DSA Rust

fn main() {
    let numbers = vec![3, 5, 1, 8, 2, 9, 4];
    // Call find_max and print the result here
    // Your code here
}

fn find_max(slice: &[i32]) -> i32 {
    if slice.len() == 1 {
        return slice[0];
    }
    let mid = slice.len() / 2;
    let left_max = find_max(&slice[..mid]);
    let right_max = find_max(&slice[mid..]);
    std::cmp::max(left_max, right_max)
}

Hint

Use println!("Maximum number is: {}", max_number); to print the result.

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)