Divide and Conquer Algorithms
View the updated (and frankly, much better) article here:
We divide the problem up to solve many smaller problems. It is just like recursion. We need to know when to stop.
Let’s say we have 8 numbers:
4 6 3 2 8 7 5 1And we want to add them all together. We divide the problem into 8 parts, which are all the numbers seperately (as seen in the example above). We then begin to add 2 numbers at a time, then 4 numbers into 8 numbers which is our resultant.
So when we get 8 individual numbers we get:
4 6 3 2 8 7 5 1
And then break it down into 4 parts we get:
4+6 3+2 8+7 5+1And so on.
Why do we break it down to 8 individual numbers and not stop at pairs of numbers since we only go back to that step anyway?
Well, what if we have an input of 1? Or an odd amount of numbers? We have to break it down to singualr numbers to deal with these cases.
A divide and conquer algorithm tries to break a problem down into as many little chunks as possible since it is easier to solve with little chunks. It typically does this with recursion.
Examples of divide and conquer include merge sort, fibonacci number calculations. This is the psuedocode for the Fibonacci number calculations:
algorithm f(n)
if n == 0 or n == 1 then
return 1
else f(n-1) + f(n+1)
Merge Sort
Merge sort is a sorting algorithm. The algorithm roughly works as follows:
- Divide the sequence of n numbers into 2 halves
- Recursively sort the two halves
- Merge the two sorted halves into a single sorted sequence
In this image we break down the 8 numbers into seperate digits.
Once we do this we can start the sorting process.
We compare 51 and 13 and place the smallest on the left and largest on the right. We do this for 10 and 64, 34 and 5, 32 and 21.
We do that for the next level as well until eventually we get a fully merged sorted list at the top.
In the second level from the top where we have 2 boxes of 4 numbers we create 2 pointers. Pointer #1 is pointing at 10 and pointer #2 is pointing at 5.
It compares 10 and 5 and since 5 is smaller than 10, it puts 5 in the list as the smallest item.
It then compares 10 and 21, 10 is smaller than 21 and we know that 10 is the smallest item in the first list (due to our sorting and merger process) so 10 is placed in the list. It does this for all the numbers until we get a fully sorted list.
It’s important to note that we are not comparing 2 lists of unsorted numbers. We are comparing 2 lists of sorted numbers. We know that 10 is the smallest in the list on the left. We know that 13 is second smallest in the list on the left.
Algorithm Merge_Sort(list)
if n > 1
copy A[1...n/2] to B[1...n/2]
copy A[(n/2 + 1)...n] to C[1...n/2]
merge_sort(b)
merge_sort(c)
merge(b, c, a)
endOur basecase here is n. If n is strictly larger than 1 then we want to divide the problem up and solve. If n is 1, if there is 1 item in the array, then the array is already sorted.
Have a look at this trace table. We have 2 lists which contain 4 items each. These lists are sorted. We want to merge them. i is the pointer in the first list, B. j is the pointer in the second list, C. K is the kth element of the new merged list.
Notice how we compare them like we did earlier.
Each node takes O(p) time when there are p integers in the list.
Each level takes O(n) time because the total number of integers at any given level is n.
There are O(log n) levels.
Therefore overall there is O(n log n) time.
Towers of Hanoi
The Towers of Hanoi is a mathematical problem which consists of 3 pegs and 3 and a number of discs. In this instance, 3 discs.
Each disc is a different size. We want to move all discs to peg C so that the largest is on the bottom, second largest on bottom — 1 etc.
We can only move 1 disc at a time.
A disc cannot be placed on top of other discs that are smaller than it.
We want to use the smallest number of moves possible.
If we have 1 disc, we only need to move it once.
If we have 2 discs, we need to move it 3 times.
We need to store the smallest disc in a buffer peg (1 move), move the largest disc to peg c (2 moves) and move the buffer disc to peg c (3 moves).
When we have 4 discs we need to make 15 moves. 5 discs is 31.
These move numbers are powers of 2 minus 1.
To find out how many moves a Tower of Hanoi solution takes you calculate (2^n)-1 where n is how many discs there are.
Notice how we need to have a buffer to store the discs.
We can generalise this problem.
If we have n discs: move n-1 from A to B recursively, move largest from A to C, move n-1 from B to C recursively.
If there is an even number of pieces the first move is always into the middle. If there are an odd number of pieces the first move is always to the other end.
ToH(numDisc, source, destination, spare)
if (numDisc > 1)
ToH(numDisc-1, source, spare, destination)Move a disc from source to destinationif (numDisc > 1)
ToH(numDisc-1, spare, destination, source)
This is what the execution tree looks like for the above algorithm with ToH(3, A, C, B).
Once we call that we 2 calls to:
- ToH(2, A, B, C)
- ToH(2, B, C, A)
Since 2 is more than 1, we move it down one more level again.
Fibonacci Numbers
The Fibonacci numbers can be found in nature. They start at 1 and the next number is the current number + the previous number. Here it’s 1 + 1 = 2. Then 2 + 1 = 3. 3 + 2 = 5 and so on.
This is the formal definition of the fibonacci numbers. If n = 0 or n = 1, output 1. Else sum the previous numbers.
Algorithm F(n)if n == 0 or n == 1 then
return 1
else
return F(n-1)+F(n-2)
N here is 6. N is more than 0 or 1, so we ignore that part.
We then calculate F(5) + F(4).
F(5) becomes F(4) + F(2).
Eventually when we get down to the base cases (when F is 0 or 1) we end up with the number 1. We return the previous number to the upper level.
So F(1) + F(0) = 2 and then we get F2 + F1 = 2 + 1 = 3.
