Divide and conquer

About This Module

Prework

Prework Reading

Pre-lecture Reflections

Lecture

Learning Objectives

Applies to a class of problem where it might be difficult to solve directly, but the problem can be easily subdivided.

If your problem is too difficult:

partition it into subproblems
solve the subproblems
combine their solutions into a solution to the entire problem

We'll look at 3 algorithms

Simple averaging
Merge Sort
Quick Sort

Warm Up: Taking the average of an array

How can we use a divide and conquer approach to taking the average of an array?

How would you do this?

fn divide_and_conquer_average(arr: &[f64]) -> (f64, usize) {
    // A divide and conquer approach to finding the average of an array using
    // recursion.
    //
    // This function takes a slice of floating point numbers and returns a tuple
    // containing the average and the number of elements in the array.
    //
    // Arguments:
    //     arr: A slice of floating point numbers
    //
    // Returns:
    //     A tuple containing the average and the number of elements in the array

    if arr.len() == 1 {
        return (arr[0], 1);
    } else {
        let mid = arr.len() / 2;
        let (left_sum, left_count) = divide_and_conquer_average(&arr[..mid]);
        let (right_sum, right_count) = divide_and_conquer_average(&arr[mid..]);
        return (left_sum + right_sum, left_count + right_count)
    }
}

let arr = [1.0, 28.0, 32.0, 41.0, 25.0];
let (total, num) = divide_and_conquer_average(&arr);
println!("The average is {}", total/num as f64);

let straightforward_avg = arr.iter().sum::<f64>() / arr.len() as f64;
println!("The straightforward average is {}", straightforward_avg);

The average is 25.4
The straightforward average is 25.4

Is this actually more efficient than the straightforward approach?

No! Why?

Answer:

We are subdividing to $lo g_{2} N$ levels and at level $n$ we are doing $2^{n}$ additions, so total

$n = 0 \sum l o g_{2} N 2^{n}$

The sum of the first $k + 1$ terms of a geometric series is:

$n = 0 \sum k r^{n} = \frac{r ^{k + 1} - 1}{r - 1}$

Plug in $r = 2$ and $k = lo g_{2} N$ and simplify.

$n = 0 \sum l o g_{2} N 2^{n} = \frac{2 ^{l o g_{2} N + 1} - 1}{2 - 1} = 2^{l o g_{2} N + 1} - 1$

Using properties of logarithms:

$2^{l o g_{2} N + 1} = 2^{l o g_{2} N} \cdot 2^{1} = N \cdot 2 = 2 N$

Final Answer:

$n = 0 \sum l o g_{2} N 2^{n} = 2 N - 1$

This holds for N a power of 2.

It is still a useful toy example though

Our plan: see two classic divide and conquer sorting algorithms

How would you do this?

Merge Sort

Recursively:

sort the first half
sort the second half
merge the results

Complexity for n elements?

Merging two lists of $Q$ and $R$ elements takes $O (R + Q)$ time, or $O (n /2 + n /2)$
$O (lo g n)$ levels of recursion: $O (n)$ work on each level
$O (n lo g n)$ time overall

BUT

Difficult to do in-place (requires extra memory allocations for intermediate results)

Implementing merging

fn merge(v1:Vec<i32>, v2:Vec<i32>) -> Vec<i32> {
    // Take two sorted vectors and merge them into a single sorted vector
    //
    // This function takes two vectors of integers and returns a new vector
    // containing all the elements from both vectors in sorted order.
    //
    // Arguments:
    //     v1: A sorted vector of integers
    //     v2: A sorted vector of integers
    //
    // Returns:
    //     A new vector containing all the elements from both vectors in sorted order

    let (l1,l2) = (v1.len(), v2.len());
    let mut merged = Vec::with_capacity(l1+l2); // preallocate memory
    let (mut i1, mut i2) = (0,0);
    
    while i1 < l1 {
        if (i2 == l2) || (v1[i1] <= v2[i2]) {
            merged.push(v1[i1]);
            i1 += 1;
        } else {
            merged.push(v2[i2]);
            i2 += 1;
        }
    }
    while i2 < l2 {
        merged.push(v2[i2]);
        i2 += 1;
    }
    merged
}

let v1 = vec![3,4,8,11,12];
let v2 = vec![1,2,3,9,22];
merge(v1,v2)

[1, 2, 3, 3, 4, 8, 9, 11, 12, 22]

Implementing Merge Sort

Now implement divide and conquer via recursion.

fn merge_sort(input:&[i32]) -> Vec<i32> {
    // Implement merge sort using divide and conquer
    //
    // This function takes a slice of integers and returns a new vector
    // containing all the elements from the input slice in sorted order.
    //
    // Arguments:
    //     input: A slice of integers
    //
    // Returns:
    //     A new vector containing all the elements from the input slice in sorted order

    if input.len() <= 1 {
        input.to_vec()
    } else {
        let split = input.len() / 2;
        let v1 = merge_sort(&input[..split]);
        let v2 = merge_sort(&input[split..]);
        merge(v1,v2)
    }
}

let v = vec![2,4,21,6,2,32,62,0,-2,8];
merge_sort(&v)

[-2, 0, 2, 2, 4, 6, 8, 21, 32, 62]

See merge_sort Cargo project if you want to debug.

Quick Sort

Select an arbitrary (random?) element $x$ from the array
Partition your vector:
- Move elements lower than $x$ to the left
- Move elements greater than $x$ to the right
- which will result in 3 partitions:
  1. the left partition
  2. the middle partition (in the correct location(s))
  3. the right partition
Repeat again for the left and right partitions

Complexity for n elements?

Partitioning $k$ elements takes $O (k)$ time
Intuition: The size of the problem usually decreases by constant factor in a recursive call
Expected time: $O (n lo g n)$ time overall (probabilistic algo analysis)
- but $O (n^{2})$ worst case when the array is already sorted and pivot is always first or last element.
- $n$ recursive calls and each level does about $n$ comparisons.

Implementing partitioning

fn partition(input:&mut [i32], pivot: i32) -> (usize,usize) {
    // move numbers lower than pivot to the left
    let mut left = 0;
    for i in 0..input.len() {
        if input[i] < pivot {
            input.swap(i,left);
            left += 1;
        }
    }
    // now input[..left] are all numbers lower than pivot

    // move numbers greater than pivot to the right
    let mut right = input.len();
    for i in (left..input.len()).rev() {
        if input[i] > pivot {
            right -= 1;
            input.swap(i,right);
        }
    }
    // input[right..]: numbers greater than pivot
    
    // left is the index of the pivot and
    // right is the index of the first number greater than pivot
    (left,right)
}

Implementing QuickSort

:dep rand
use rand::Rng;

fn quicksort(input:&mut [i32]) {
    if input.len() >= 2 {    
        // pivot = random element from the input
        let pivot = input[rand::rng().random_range(0..input.len())];

        // partition the input array around the pivot
        let (left,right) = partition(input, pivot);
        println!("\nL {} R {} P {} P {}", left, right, pivot, input[left]);
        
        println!("Left side {:?}", &input[..left]);
        println!("Right side {:?}", &input[right..]);
        
        quicksort(&mut input[..left]);
        quicksort(&mut input[right..]);
    }
}

let mut q = vec![145,12,3,7,83,12,8,64];
quicksort(&mut q);
println!("{:?}", q);

L 7 R 8 P 145 P 145
Left side [12, 3, 7, 83, 12, 8, 64]
Right side []

L 6 R 7 P 83 P 83
Left side [12, 3, 7, 12, 8, 64]
Right side []

L 5 R 6 P 64 P 64
Left side [12, 3, 7, 12, 8]
Right side []

L 1 R 2 P 7 P 7
Left side [3]
Right side [12, 12, 8]

L 1 R 3 P 12 P 12
Left side [8]
Right side []
[3, 7, 8, 12, 12, 64, 83, 145]

See quicksort Cargo project to single step debug.

Recap of Divide and Conquer algorithms

They divide the problems into smaller subproblems
They are always polynomial in execution time
They tell us nothing about P and NP

Note on Recursion in Rust

Recursion with mutable references can be quite hard in Rust due to the borrow checker

A relatively simple example of the problem.

We want to make another mutable reference to the first element and pass the rest of the slice to the recursive call.

fn process_slice(slice: &mut [i32]) {
    if !slice.is_empty() {
        let first = &mut slice[0]; // Mutable borrow of the first element
        process_slice(&mut slice[1..]); // Recursive call borrows the rest of the slice mutably
        *first *= 2; // Attempt to modify the first element after recursive call
    }
}

fn testme() {
    let mut numbers = [1, 2, 3, 4];
    process_slice(&mut numbers);
    println!("{:?}", numbers);
}

testme();

[E0499] Error: cannot borrow `*slice` as mutable more than once at a time

   ╭─[command_2:1:1]

   │

 3 │         let first = &mut slice[0]; // Mutable borrow of the first element

   │                     ──────┬──────  

   │                           ╰──────── first mutable borrow occurs here

 4 │         process_slice(&mut slice[1..]); // Recursive call borrows the rest of the slice mutably

   │                            ──┬──  

   │                              ╰──── second mutable borrow occurs here

 5 │         *first *= 2; // Attempt to modify the first element after recursive call

   │         ─────┬─────  

   │              ╰─────── first borrow later used here

───╯

The unsafe language feature allows you to bypass the borrow checker but it is not recommended and not covered in this class. A very small example below

fn process_slice(slice: *mut i32, len: usize) {
    if len == 0 {
        return;
    }

    unsafe {
        // Access and modify the first element
        let first = &mut *slice;

        // Recursive call with the rest of the slice
        let rest = slice.add(1); // Advance the pointer to the next element
        process_slice(rest, len - 1);

        *first *= 2;
    }
}

fn testme() {
    let mut numbers = [1, 2, 3, 4];
    let len = numbers.len();

    unsafe {
        process_slice(numbers.as_mut_ptr(), len);
    }

    println!("{:?}", numbers); // Output: [2, 4, 6, 8]
}
testme();

[2, 4, 6, 8]

DS210 Course Notes