Project Euler is an interesting website that has a good amount of number theory and algorithmic problems. These are brain teasers that help keep your skills sharp, and may teach you a thing or two about new algorithms down the pipeline. There are many spoiler websites out there, so showing the interesting solution to a handful of these problems doesn't seem like a problem. We'll show number 67 today, and perhaps in the future we'll show others that are relevant to a specific algorithm.

Problem 67, Divide and Conquer Algorithm

In general, divide and conquer is a recursive solution, trying to solve smaller and smaller problems until the smallest problem could be solved in a straightforward manner. It uses three steps: divide, conquer, and combine. An example of this is merge-sort, where one divides the $n$ element array to be sorted into two subarrays of $\frac{n}{2}$ elements. Then each of these arrays is sorted recursively using this method (or using insertion sort if the list is short enough -- usually below 7 elements depending on the processor). Finally, the two sorted lists are combined or "merged" together to give the final sorted answer.

From Project Euler, problem 67 has a slick solution using the divide and conquer method.

Definition of Problem

We define a triangle with values between "00" and "99" inclusive. Each row $n$ contains $n$ values. Traversing the triangle from top to bottom, only being able to move from $m$ (the current column) to $m$ or $m+1$ in the subsequent row. Start at $n=1$, $m=1$. What is the greatest possible sum when reaching the bottom of the triangle?

Brute Force Solution

Enumerate each path, and add all the numbers in the path. Take the maximum of all of your summations.

My Solution (spoiler)

a = "75\n\
95 64\n\
17 47 82\n\
18 35 87 10\n\
20 04 82 47 65\n\
19 01 23 75 03 34\n\
88 02 77 73 07 63 67\n\
99 65 04 28 06 16 70 92\n\
41 41 26 56 83 40 80 70 33\n\
41 48 72 33 47 32 37 16 94 29\n\
53 71 44 65 25 43 91 52 97 51 14\n\
70 11 33 28 77 73 17 78 39 68 17 57\n\
91 71 52 38 17 14 91 43 58 50 27 29 48\n\
63 66 04 68 89 53 67 30 73 16 69 87 40 31\n\
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"
height = 15
orig = list()
ss = a.split("\n")
summer = list()
for i in range(height):
  s = ss[i]
  orig.append(list())
  summer.append(list())
  for j in range(i+1):
    orig[i].append(int(s[j*3:j*3+2]))
    summer[i].append(0)

summer[0][0] = orig[0][0]

for i in range(1,height):
  for j in range(i+1):
    if(j == 0):
      summer[i][j] = summer[i-1][j]+orig[i][j]
    elif(j == i):
      summer[i][j] = summer[i-1][j-1]+orig[i][j]
    else:
      #pick the greater of the two choices above the current position
      m = max(summer[i-1][j-1],summer[i-1][j])
      summer[i][j] = m + orig[i][j]

print max(summer[height-1])

Here, we keep a running total of the max sum at each position in the triangle we have examined. We traverse top down, and pick the "best" case (greatest number) of the two choices above each position (the $m-1$ or $m$ column). The base cases are along the edges of the triangle, where there is only one choice ($m$ for the left edge, $m-1$ for the right edge).

Runtime Analysis

Brute force: $O(2^n+2^n)$ each path has to be enumerated and added, and then the max has to be calculated, so the final answer is $O(2^n)$.

Divide and Conquer: $O(\frac{n\cdot (n-1)}{2}+n)$. Each element in the triangle has a constant number of operations performed on it, and then the max has to be calculated in the last row. Final runtime: $O(n^2)$.

Viewing these graphs of runtime using Wolfram Alpha (keyword = "plot | 2^n, n^2 | n = 1 to 12"), we see that my solution is orders of magnitude faster than brute forcing the solution:

References

Algorithms--Cormen, Leiserson, Rivest, Stein