Use of Divide and Conquer

Tradition attributes the origin of the motto to Philip II of Macedon. In politics and sociology it is about gaining and maintainng power by breaking up larger concentrations of power into pieces that individually have less power!

In Computing this technique can be divided into the following three parts:

1-Divide: This involves dividing the problem into some sub problem.

2-Conquer: Sub problem by calling recursively until sub problem solved.

3-Combine: The Sub problem Solved so that we will get find problem solution. 

Starter

The class can act out calls to a merge sort algorithm - see below for an explanation.

Take a shuffled pile of cards with numbers written on them. Creating clones of yourself from students you pass out piles of cards to two others, who each pass half their cards to two more clones they make behind them. This continues till there is a row of people each holding one card only. The cards are then passed back the way they came in a way that means when the cards are passed back to you, magically they are no longer random but now in sorted order.

https://teachinglondoncomputing.files.wordpress.com/2015/10/props-sortingcards-1-32.pdf

Suggested Video

Algorithms to look at

We begin looking at algorithms, sorted by the techniques they use.

Here are the steps involved:

1-Divide: Divide the given problem into sub-problems using recursion.

2-Conquer: Solve the smaller sub-problems recursively. If the subproblem is small enough, then solve it directly.

3-Combine: Combine the solutions of the sub-problems that are part of the recursive process to solve the actual problem.

Sorting

Problem class SORT:

Input: an array a of integers.

Output: an array with all elements of a in increasing order.

example:

        +----+----+----+----+----+----+----+----+
    a = | 19 |  1 | 29 | 30 |  6 | 15 |  2 |  5 |
        +----+----+----+----+----+----+----+----+

        +----+----+----+----+----+----+----+----+
 return |  1 |  2 |  5 |  6 | 15 | 19 | 29 | 30 |
        +----+----+----+----+----+----+----+----+

MergeSort

Algorithm Merge-Sort(a)
if a's length > 1 then
  x <- first half of a
  y <- second half of a
  Merge-Sort(x)
  Merge-Sort(y)
  a <- Merge(x, y)
fi

example:

                           |  +----+----+----+----+----+----+----+----+
                           |  |  1 |  2 |  5 |  6 | 15 | 19 | 29 | 30 |
                           |  +----+----+----+----+----+----+----+----+
                           |
        +----+----+----+----+----+----+----+----+
        | 19 |  1 | 29 | 30 |  6 | 15 |  2 |  5 |
        +----+----+----+----+----+----+----+----+
                      |           |
+----+----+----+----+ |           |  +----+----+----+----+
|  1 | 19 | 29 | 30 | |           |  |  2 |  5 |  6 | 15 |
+----+----+----+----+ |           |  +----+----+----+----+
                      |           |
     +----+----+----+----+     +----+----+----+----+
     | 19 |  1 | 29 | 30 |     |  6 | 15 |  2 |  5 |
     +----+----+----+----+     +----+----+----+----+
            |    |                          |   |            
+----+----+ |    | +----+----+  +----+----+ |   | +----+----+
| 19 |  1 | |    | | 29 | 30 |  |  6 | 15 | |   | |  2 |  5 |
+----+----+ |    | +----+----+  +----+----+ |   | +----+----+
            |    |                          |   |            
  +----+----+    +----+----+      +----+----+   +----+----+
  | 19 |  1 |    | 29 | 30 |      |  6 | 15 |   |  2 |  5 |
  +----+----+    +----+----+      +----+----+   +----+----+
     /   \         /     \         /      \        |      \
+----+  +----+  +----+  +----+  +----+  +----+   +----+  +----+
| 19 |  |  1 |  | 29 |  | 30 |  |  6 |  | 15 |   |  2 |  |  5 |
+----+  +----+  +----+  +----+  +----+  +----+   +----+  +----+

Merging

Algorithm Merge(x, y)
x_pos <- 0, y_pos <- 0, a_pos <- 0
while x_pos < x.length and y_pos < y.length do
  if x[x_pos] < y[y_pos] then
    a[a_pos] <- x[x_pos]
    x_pos <- x_pos + 1
  else
    a[a_pos] <- y[y_pos]
    y_pos <- y_pos + 1
  fi
  a_pos <- a_pos + 1
od
append x[x_pos...x.length] to a
append y[y_pos...y.length] to a
return a

example:

 +----+----+----+----+
 |  1 | 19 | 29 | 30 |
 +----+----+----+----+\    +----+----+----+----+----+----+----+----+
                       >-->|  1 |  2 |  5 |  6 | 15 | 19 | 29 | 30 |
 +----+----+----+----+/    +----+----+----+----+----+----+----+----+
 |  2 |  5 |  6 | 15 |
 +----+----+----+----+

Advanced/Extra reading: How Much Time?

Write a recurrence.

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

The Master Theorem (p 73) solves this. For T(n) = a T(n / b) + f(n):

• if f(n) = O(n^(log_b a - eps)) for some eps > 0, then T(n) = O(n^(log_b a))
• if f(n) = O(n^(log_b a)), then T(n) = O(n^(log_b a) log n)

For Merge-Sort, then, where a = 2 and b = 2