Day 29: CM, Page 15

Day 29: I've skipped a couple of days. This is the last page of chapter one - one more page of the Josephus problem. The authors do one final generalization of the Josephus problem. Suppose we take our previous recurrence:

f(1) = alpha
f(2n+j) = 2f(n) + BetaSubJ

And generalize it to:

f(j) = alphaSubJ where 1 <= j <= d
f(dn+j) = cf(n) + betaSubJ where 1 < = j <= d and n >= 1

Given any recurrence that fits this pattern, we can solve it by converting from a number in base d to a number in base c (as we did yesterday for the base 2 to base 2 conversion). For example, suppose we have the recurrence:

f(1) = 1
f(2) = 2
f(3n) = 10f(n) + 1
f(3n+1) = 10f(n) - 2
f(3n+2) = 10f(n) + 3

To calculate f(10):
10 = 101 base 3
f(10) = f((101)b3) = (1 1 -2)b10 = 100 + 10 - 2 = 108

Pretty neat. That's it for chapter 1.

Day 28: CM, Page 15

Day 28: The authors continue to generalize the Josephus problem. We noticed a few days ago that the Josephus problem can be represented as cyclic left bit shift. Can we generalize that observation to our more general equations with alpha, beta, and gamma? Yes, we can...

First, rewrite our recurrences as:
f(1) = alpha
f(2n + j) = 2f(n) + betaSubJ for j=0,1 and n>=1

For j=0, betaSubJ = beta and for j=1, betaSubJ = gamma. Then by the equations above:

Sure enough, if we consider the original problem with alpha=1, beta=-1, gamma=1, we have something like:

100 = (1100100)
f(1100100) = alpha gamma beta beta gamma beta beta
f(1100100) = (1 1 -1 -1 1 -1 -1) = 64 + 32 - 16 - 8 + 4 - 2 - 1 = 73

We've had to "relax" the binary representation to allow betas and gammas that are not equal to 0 or 1. But this is still and interesting result.

One more page of the Josephus problem tomorrow and then it's on to the exercises.

Day 27: CM, Page 14

Day 27: The authors introduce the repertoire method by an example with the Josephus problem. Recall from yesterday that we believe:

A(n) = 2^m
B(n) = 2^m - 1 - l
C(n) = l

How can we prove this? One way is to find a series of equalities based on specific data points, then to solve those equalities. No hints yet on how to find the specific data points to form the equalities. The authors make a few clever observations to find their data points. We'll assume that f(n) = A(n)(alpha) + B(n)(beta) + C(n)(gamma).

What happens in the case where alpha=1, beta=0, gamma=0? We have f(n) = A(n) or:

A(1) = 1
A(2n) = 2A(n)
A(2n+1) = 2A(n)

We want to show that A(n) = 2^m. This follows from the equations above by induction. A(1) = 1 since A(1) = alpha. Assume A(n/2) = 2^(m-1). Then:

A(n) = A(2^m + l) = 2A((2^m + l)/2) = 2(2^(m-1)) = 2^m.

Next we want some other interesting data points. What are some other values for alpha, beta, and gamma that make it easy to solve our recurrences? How about f(n) = 1:

1 = alpha
1 = 2*1 + beta
1 = 2*1 + gamma

For this to be true, alpha=1, beta=-1, and gamma=-1. Plugging that back in, we get:

A(n) - B(n) - C(n) = f(n) = 1

What happens if f(n) = n? In that case:

1 = alpha
2n = 2n + beta
2n+1 = 2n + gamma

So in this case, alpha=1, beta=0, and gamma=1. Plugging that back in, we get:

A(n) + C(n) = n

Now that we have three inequalities, we can solve them. From our first observation, we directly have A(n) = 2^m

That gives us:
A(n) + C(n) = n
C(n) = n - A(n) = 2^m - l - 2^m = l

Which matches what we expect. And finally:

A(n) - B(n) - C(n) = 1
B(n) = A(n) - C(n) - 1
B(n) = 2^m - l - 1

And that matches all our observations for A(n), B(n), and C(n) of:

A(n) = 2^m
B(n) = 2^m - l - 1
C(n) = l

This is an illustration of the repertoire method. There are still some questions to work out - how do we choose the right specific data points to use for our equalities? I suspect we'll return to this in the exercises. More on the Josephus problem tomorrow.

Day 26: CM, Page 13

Day 26: The Josephus problem continued. The authors generalize the Josephus problem even further. They ask the question: how would we find a closed form for the recurrence if the pattern had been more complex? What if the coefficients on the recurrence were something besides -1 and +1? To generalize the recurrence:


By expanding the recurrence, we can build a table of values for f(n):


If we write f(n) as:
Then, it appears that:
More on these equations tomorrow.

Day 25: CM, Page 12

Day 25: I've missed a couple of days. I'm now on pace for Nov 5, 2016.

The authors continue to examine the binary representation of the Josephus function. They observe that since the solution to the Josephus problem is a cyclic left bit shift, you might expect that m iterations of the function would return to the original number. However, this is not true because zeros are removed from the number during the shifting process. For example:

J(1101) = 1011
J(1011) = 0111 = 111
J(111) = 111

For a given number, you can find the convergent number by counting the number of 1's in the original number's binary representation. The point of convergence can be defined as 2^v(n) - 1 where v(n) is the numbers of 1's in n.

More on the Josephus problem tomorrow. The authors continue to generalize it even further.

Day 24: CM, Page 11

Day 24: The authors prove the closed form of the Josephus problem by induction. They prove the odd and even cases separately.

Base case: J(1) = J(2^0 + 0) = 2(0) + 1 = 1
Assume: J(2n) = 2(J(n)) - 1 and J(2n + 1) = 2(J(n)) + 1
Inductive Hypothesis Even: J(n/2) = J(2^(m-1) + l/2) = 2l/2 + 1
Inductive Hypothesis Odd: J((n-1)/2) = J(2^(m-1) + (l-1)/2) = 2(l-1)/2 + 1

This a different twist on the normal induction process. Rather than assuming n-1 is true, we are assuming n/2 is true for all even numbers. Then:

And a similar proof for odd numbers:


Together, the two proofs cover all even and odd numbers. Next the authors suggest trying to generalize the problem. There seems to be a relationship in the problem between powers of 2, so let's represent the problem in binary.


That last step follows because J(n) = 2l + 1 and b sub m = 1. This is a pretty interesting result. J(n) can be calculated by doing a one bit cyclic left shift on n. More details from the CM authors tomorrow about this new observation tomorrow.

Day 23: CM, Page 10

Day 23: The Josephus problem continued. Yesterday we found a recursive solution for the Josephus problem with an even number of people. With an odd number of people, the recursive solution is similar.

Consider J(2n + 1). If you start with 1 2 3 4 5 6 7 8 9, after the first round of elimination you have 1 3 5 7 9. But wait! This isn't right. To continue the elimination process, we would need to eliminate 1 next, so new sequence isn't quite correct - it's off by one if we want to skip the first member of the sequence on the second iteration. To keep the iteration consistent (always skipping the first element in a sequence), we need to eliminate one more element. So 1 2 3 4 5 6 7 8 9 is actually the same as 3 5 7 9 where 1 is included in the first round of elimination. Now on the second round of iteration we start with 5 as expected. 3 5 7 9 is the same problem as 1 2 3 4 except that each number is doubled and incremented by 1. So J(2n + 1) = 2(J(n)) + 1.

So we have:
J(1) = 1
J(2n) = 2(J(n)) - 1
J(2n + 1) = 2(J(n)) + 1

And with that we have a recursive formula to describe a solution to the problem. The authors use the recursive formula to describe the pattern we saw a couple of days ago, but they find a better notation to represent the closed form.

J(n) = J(2^m + l) = 2l + 1

Where 2^m <= n < 2^(m+1) and l is the remainder (or leftover) of n/2^m. Also note: l < 2^m

With this we have a closed form representation of the Josephus problem. Tomorrow we'll need to prove it, and authors have some additional interesting observations about the problem.

Day 22: CM, Page 9

Day 22: The authors examine the Josephus problem. They start by looking at small examples. When they fail to find a pattern, they try to find a recurrence. Rather than finding a single equation, they break the problem into even and odd numbers of people.

Starting with an even number of people, after the first round we're left with exactly half as many people.

1 2 3 4 5 6 7 8 9 10
1 3 5 7 9

1 3 5 7 9 is the same as 1 2 3 4 5 except that each person's number is double and decreased by 1. So:

J(2n) = 2(J(n)) - 1

In other words 1 2 3 4 5 6 7 8 9 10 will have the same solution as 1 2 3 4 5 where each number is doubled (2 4 6 8 10) and decreased by 1 (1 3 5 7 9) since we know all the even numbers in the first sequence will be eliminated. The key here is that the authors have found a notation that allows the problem to be expressed as a sub-problem of itself. Pretty ingenious!

We'll take a look at odd numbers tomorrow.

Day 21: CM, Page 8

Day 21: The authors find a cleaner solution to zig problem. Rather than derive the closed form by expanding a recurrent form, they notice a relationship between zigs and lines in a plane. A zig is the same as two intersecting lines except that the lines don't continue after they meet. Since the lines in both problem only intersect one another once, we don't need to worry about intersection after the zig if we always ensure the lines intersect before the zig. And if the lines intersect before the zig, we'll have the same number of regions as lines in plane minus the regions after the zig. For each zig, we only loose two regions (one for each line that is lost). So zigs are related to lines in a plane as follows:

Z(n) = 2(L(n)) - 2n

If we expand that we have:

2(n(n+1))/2 + 1 - 2n =
n^2 + n + 1 - 2n =
n^2 -n + 1

Which matches what we found yesterday.

Next the author introduces the Josephus problem. There is a story behind this problem. Josephus was a famous historian of the first century. During the Jewish-Roman war, Josephus was trapped in a cave with 40 other Jewish rebels. They decided to kill themselves rather than surrender. They got in a circle and had every third person kill himself. Josephus and a conspriator decided they didn't want to kill themselves and quickly calculated where to position themselves in the circle so that they were the last ones standing. How did Josephus perform the calculation?

Reading ahead a little authors begin by looking at the same problem, but hop two people instead of three. Lets look at some small examples where every second person is killed.
J(1) = 1
J(2) = 1
J(3) = 3
J(4) = 1
J(5) = 3
J(6) = 5
J(7) = 7
J(8) = 1
J(9) = 3
J(10) = 5
J(11) = 7
J(12) = 9
J(13) = 11
J(14) = 13
J(15) = 15
J(16) = 1

So it appears that the solution depends on n's position relative to the most recent power of 2. It looks like J(n) = 1 + 2(n - "last power of 2")

J(3) = 1 + 2(3-2) = 3
J(4) = 1 + 2(4-4) = 1
J(11) = 1 + 2(11 - 8) = 7
J(15) = 1 + 2(15 - 8) = 15

Tomorrow, we'll see how the authors approach the problem. Here's a statue of Josephus:

Day 20: CM, Page 7

An expression for a quantity f(n) is in closed form if we can compute it using at most a fixed number of "well known" standard operations, independent of n.
Concrete Mathematics, p.7

Day 20: The authors point out that we haven't really proven that our closed form matches the recurrent equations for lines in plane. How do we prove it? We can use the same technique that was used for the Tower of Hanoi.

Trying to prove: L(n) = n(n+1)/2 + 1
Base case: L(0) = 1 (with no lines, we have one region - matches recursive form).
Inductive Hypothesis: Assume the closed form (n(n+1)/2)+1 holds for n-1.
Assume L(n) = L(n-1) + n is true

Then:
So by induction, L(n) = n(n+1)/2 + 1 is true.

The authors go on to discuss closed forms. The general idea is that a closed form cannot have "..."s in it. We must be able to use a fixed number of "well known" operations to solve a closed form equation. Some recurrences don't have closed forms. In those cases, if the recurrences are important, we can invent new notation that allows us to treat them as closed form. For example, n! is considered closed form even though it is defined recursively. It is important enough and simple enough that we allow it to be part of our closed form equations.

Finally, a variation on the "lines in a plane" problem is presented: "zigs in a plane". A zig in plane is like a ">" - two lines that meet at a point and stop. One zig creates two regions - one region on one side of the zig and one on the other side. So Z(1) = 2.

Before reading ahead I took a stab at the problem. The authors come up with a much simpler solution on the next page, but here's one way to approach the problem.

First, look at easy cases.
Z(0) = 1 (no zigs, one region)
Z(1) = 2 (one zig, two regsions)
Z(2) = 7
Z(3) = 16

After n=3, it gets hard to draw the picture. From the small cases above, it's hard to find a definite pattern. Let's see if we can find a recursive equation. I approached this problem roughly the same way I approached lines in a plane. I tried to understand how many regions were formed as lines crossed one another. For n=1, there are no lines to cross, so I take n=0 and n=1 as base cases. Next, I look at n=2. For n=2, the first line in the zig crosses both lines from n=1. Each time it hits a line it forms a new region (2 new regions). The zig crosses the two lines again. It forms a new region when it hits each line plus one new region when it crosses the last line (3 new regions). So we have a total of 2 + 3 new regions or 2(n-1) + 2(n-1) + 1 regions.

So the recursive formula looks like:
Z(0) = 1
Z(1) = 2
Z(n) = Z(n-1) + 4n - 3

Testing on a few small numbers, this works.
Z(2) = 2 + 4(2) - 3 = 7
Z(3) = 7 + 4(3) - 3 = 16

Now, let's see if we can find a closed form. We'll try the same method we used last time and unwind the recursive formula.

Z(n) = Z(1) + ... + Z(n-3) + (4(n-2) -3) + (4(n-1) - 3) + (4n - 3)

There is a lot of repetition here. We should be able to pull out some of the common patterns. -3 appears n-1 times. It is n-1 rather than n because Z(1) is part of our base case and we do not expand it. 4n also appears n-1 times. What we have left is ... - 4(2) - 4(1) - 4(0). This look like a triangular number times -4. The sum only goes to n-2 because Z(1) is not expanded and and the nth term in the expansion has 4(0). Putting it all together we have:


Now let's see if we can prove it by induction.

Base case - we'll do a few just for extra confirmation:
Z(0) = 2(0^2) - 0 + 1 = 1
Z(1) = 2(1^2) - 1 + 1 = 2
Z(2) = 2(2^2) - 2 + 1 = 7

We'll assume our recursive formula is correct Z(n) = Z(n-1) + 4n - 3
And we'll assume our inductive hypothesis is true - that our closed form is correct for n-1.

So the formula is true by induction. One curious thing about these inductive proofs is that we need to assume the recursive form is correct, but we have not rigorously proved that it is correct. The authors currently seem more concerned with problem solving tools than giving a rigorous proof, so we won't worry about it for now.

Tomorrow, we'll look at a different approach to the zig problem.

Day 19: CM, Page 6

We can often understand a recurrence by "unfolding" or "unwinding" it all the way to the end.
- Concrete Mathematics, p. 6

Day 19: More discussion of lines in the plane. The authors suggest that the recurrence that defines the max number of regions defined by n lines in a plane is:

L(0) = 1
L(n) = L(n-1) + n

See yesterday's post for more background on the problem.

The authors point out a new technique for finding the closed form solution: unwind a recursive formula.

L(n) = L(n-1) + n
L(n) = L(n-2) + (n-1) + n
L(n) = L(n-3) + (n-2) + (n-1) + n
...
L(n) = L(0) + 1 + 2 + ... + (n-2) + (n-1) + n

We know from earlier posts, that the sequence 1 + 2 + ... + (n-1) + (n-1) + n is equal to n(n-1)/2.

That's it for today. Not too much new. More on lines in the plane tomorrow.

Day 18: CM, Page 5

Day 18: We're done with the Tower of Hanoi. The authors look at a different problem that will us practice the analytical skills we just learned. The question is: "What is the maximum number L(n) of regions defined by n lines in the plane?" First we look at small cases:


This picture skips n = 0 which is 1 - there is one region if there are no lines. From the sequence above, a pattern jumps out. The difference between the number of regions for each value of n is 1, 2, 3, 4. This is the same pattern as the difference between triangular numbers. In fact, the numbers look like 1 + (n(n+1)/2). But what if we didn't notice the pattern? Is there a more logical approach to this problem?

For each region that we split with a line, we make two regions - one region on one side of the line, and one region on the other side of the line. So if we split k regions, we make k new regions. So how do regions relate to the number of lines? It looks like we need to cross k-1 lines to make k regions. I'm not sure how to prove this.. but the idea is roughly as follows: when a new line hits the first line it will intersect, it has crossed one region and thus formed one new region; each line it hits after that forms one more region. As it crosses the last line and enters the final region, it forms one last region. So for each line we hit, we form one region except for the last line where we form two regions. Thus for k-1 intersected lines, we form k regions. Assuming that none of the lines we draw is parallel, the nth line will intersect all previous n-1 lines in one spot. That means it will form n new regions. So L(n) = L(n-1) + n for n > 0.

More on intersecting lines tomorrow.

Day 17: CM, Page 4

One of the main objecties of this book is to explain how a person can solve recurrences without being clairvoyant.
- Concrete Mathematics p. 4

Day 17: The authors give an outline for solving problems like the Tower of Hanoi:

1. Look at small cases...
2. Find and prove a mathematical expression for the quantity of interest...
3. Find and prove a closed form for our mathematical expression...
- CM p.4

This is the approach we just went through yesterday for the Tower of Hanoi. The authors explain that the rest of the book is focused on helping us find closed forms without brilliant leaps of insight. They give an example of one technique: change the form of an equation to reveal underlying patterns.

Suppose U(n) = T(n) + 1. Then if we add one to both sides of our recurrence, we have:
T(0) + 1 = 1
T(n) + 1 = 2(T(n-1)) + 2 = 2(T(n-1) + 1)

So:
U(0) = 1
U(n) = 2(U(n-1))

After restructuring the problem slightly, it is clear that the closed form of U(n) is 2^n. So T(n) = U(n) -1 = 2^n - 1.

To rephrase the author's suggestion, when solving a problem like this, we need to:
1. Look at small cases
2a. Find some notation that provides an answer to the problem.
2b. Try to represent the solution so that the underlying pattern or structure is more apparent.
2c. Try to find a different way to look at the problem (e.g. binomial coefficients can be looked at probabilistically or as a summation).
3. Based on the tricks above (plus any others), find a closed form.

Tomorrow we'll look how to slice a pizza to achieve maximum slices.

Day 16: CM, Page 3

Day 16: We learn some basic vocabulary today.

"... a recurrence (a.k.a. recurrence relation or recursion relation)... gives a boundary value and equation of the general value in terms of earlier ones" (CM p.3).

The following equalities define a recurrence for the Tower of Hanoi problem:
T(0) = 0;
T(n) = 2(T(n-1)) + 1;

The first equation is the boundary value of the equation. The second equation is general value - it is defined in terms of earlier values.

Notice that if n is very large, it is hard to compute T(n) - you need to know all the previous values. The recurrence defines local information or relative information. What we'd like is a closed form. The authors don't define a closed form yet, but the general idea is we'd like an equation that would let us calculate T(n) directly without knowing previous values.

How do we find a closed form? The authors suggest that one way is to guess the closed form and then prove that it is true. We can guess the closed form by looking at small cases first. If we look at the first six values, we have:
T(0) = 0
T(1) = 1
T(2) = 3
T(3) = 2*3+1 = 7
T(5) = 2*7+1 = 15
T(6) = 2*15+1 = 31

It looks like T(N) = 2^n - 1. To prove it, we can use induction. "Mathematicl induction is a general way to prove that some statement about the integer n is true for all n >= n sub 0." First you prove the statement for the first integer, n sub 0. This is called the basis. Next you assume you have proven the statement for all values between n sub 0 and n-1. Then you prove the statement for n. This is called the induction.

To see how induction works, let's try to prove the closed form of the recurrent equations above. The basis in this case is n=0. It is easy to prove: T(0) = 0 since it takes no moves to move no disks. And 2^0 - 1 = 0. So the basis holds. Now let's assume our recurrence above is true and T(n) = 2(T(n-1)) + 1. Let's also assume the formula we are trying to prove is true for n-1: T(n-1) = 2^(n-1) - 1. Substituting our closed form for n-1 into our recurrence for n gives: T(n) = 2(2^(n-1) -1) + 1= 2^n - 1. Therefore the closed form is also true.

Let's get some different points of view on the terminology introduced on this page.

In mathematics, a recurrence relation is an equation that defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms... Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function of n.
-wikipedia

The wiki page also has a discussion of different methods for finding closed forms of recurrence relations. Here is a definition of closed forms from wikipedia:

In mathematics, an expression is said to be a closed-form expression if, and only if, it can be expressed analytically in terms of a bounded number of certain "well-known" functions. Typically, these well-known functions are defined to be elementary functions; so infinite series, limits, and continued fractions are not permitted. Similarly, an equation or system of equations is said to have a closed-form solution if, and only if, at least one solution can be expressed as a closed-form expression.
-wikipedia

And here is a description of mathematical induction:

Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one
-wikipedia

Note: this is different than inductive reasoning. Inductive reasoning is drawing conclusiong based on a limited series of observations. For example: if all the ice I've touched is cold, then ice is cold.

Here is a further description of mathematical induction:

The simplest and most common form of mathematical induction proves that a statement involving a natural number n holds for all values of n. The proof consists of two steps:

1. The basis (base case): showing that the statement holds when n = 0.
2. The inductive step: showing that if the statement holds for some n, then the statement also holds when n + 1 is substituted for n.

The assumption in the inductive step that the statement holds for some n is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for n + 1.

The description above of the basis applies when 0 is considered a natural number, as is common in the fields of combinatorics and mathematical logic. If, on the other hand, 1 is taken to be the first natural number, then the base case is given by n = 1.

This method works by first proving the statement is true for a starting value, and then proving that the process used to go from one value to the next is valid. If these are both proven, then any value can be obtained by performing the process repeatedly. It may be helpful to think of the domino effect; if one is presented with a long row of dominoes standing on end, one can be sure that:

1. The first domino will fall
2. Whenever a domino falls, its next neighbor will also fall,

so it is concluded that all of the dominoes will fall, and that this fact is inevitable.

-wikipedia

Day 15: CM, Page 2

... we'll see repeatedly in this book that it's advantageous to LOOK AT SMALL CASES first.
- Concrete Mathematics p.2

The next step in solving the problem is to introduce appropriate notation: NAME AND CONQUER.
- Concrete Mathematics p.2

Day 15: Two of the most important tools in problem solving are introduced: look at small cases and find a good notation. Looking at small cases is especially important. This is useful for problem solving in almost any context. It's often easy to spot patterns by examining the simplest cases first.

For Tower of Hanoi problem, the authors note that T(1) = 1 (it takes one move to move one disk), T(2) = 3 (it takes three moves to move two disks) and T(0) = 0 (it takes no move to move no disks). How would we move three disks? We already have a way to move 2 disk, so first we would move two disks, then we would move the third disk, and finally we would move the two disks back onto the third. This is a recursive solution. If we can solve the problem for T(n-1), we can solve it for T(n).

The authors use the observation above to show that T(n) <= 2(T(n-1)) + 1. This is true, because we can move the top n-1 disks to one peg, move the bottom disk, then move the n-1 disks onto the bottom disk. We know this solution takes 2(T(n-1)) + 1 moves, but maybe there is a solution that takes fewer moves? Nope. The authors point out that when we move the nth disk, the other n-1 disks must be on another peg. So in the best case, we still need to move n-1 pegs to the other disk. There's no other option. So T(n) >= 2(T(n-1)) + 1 (it's possible you could do worse than 2(T(n-1)) + 1 if you make bad moves).

That's it for page 2. More on the Tower of Hanoi tomorrow.

Day 14: CM, Page 1

Day 14: The first page of Concrete Mathematics. "This chapter explores three sample problems that give a feel for what's to come... their solutions all use the idea of recurrence" (CM p.1)

The first page explains the Tower of Hanoi problem. "We are give a tower of eight disks, initially stacked in decreasing size on one of three pegs. The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller" (CM p.1). This is a famous problem in computer science. Most CS students are exposed to it at some point. The picture below shows a solution with four disks.


Here is a brief description of the legend behind the problem:

There is a legend about a Vietnamese or Indian temple which contains a large room with three time-worn posts in it surrounded by 64 golden disks. The priests of Brahma, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle, since that time.... According to the legend, when the last move of the puzzle is completed, the world will end.
- wikipedia

There is no discussion of a solution on the first page, only a description of the problem. We'll save discussion of the solution for tomorrow.

Day 13: CM, Page xii

Day 13: The last page of the table of contents and the last page before the main part of the book. The second half of the book covers binomial coefficients, "special numbers", generating functions, discrete probability, and asymptotics. I also just realized that there are 100 pages of answers and 30 pages of bibliography, and 20 pages of index. I hope that 150 days isn't too boring.

We've already looked at binomial coefficients a little, and "special numbers" (Stirling Numbers and Fibonacci Numbers), but what are generating functions and asymptotics?

"In mathematics a generating function is a formal power series whose coefficients encode information about a sequence a_n that is indexed by the natural numbers" (wikipedia).

An ordinary generating function is defined by:

The summation produces a sequence like:


The coefficients on the power series are 1, 1, 1, 1.... So this is the generating function for the sequence containing all ones. The sum's equality to 1/(1-x) holds for x in (-1,1). Not all generating functions will converge or have closed forms and some generating functions (like the one above) will only have closed forms for a range of numbers. For 1/(1-x) and x > 1, the sum clearly does not converge and does not match the closed form. However, for x < 1, the sum does converge. You can see that the equality holds under these conditions by multiplying both sides of the equation by (1-x):


Where m is a number approaching infinity. As m approaches infinity for x > 1, x^m approaches a giant number, so the closed form does not hold for |x| > 1. We'll get to learn much more about generating functions in a few hundred days.

Day 12: CM, Page xii

Day 12: The first page of table of contents. In the next 200 days or so we'll cover recurrent problems, sums, integer functions, number theory, and part of a chapter on binomial coefficients. A couple of sections jump out due to their fancy names.

Independent Residues: Not even wikipedia knows what this is.

Phi and Mu: Nor this. Unless it's talking about "the second oldest female fraternal organization established in the United States".

Day 11: CM, Page xi

Day 11: A second page of notation. I'm going to practice my LaTeX on this page.

The link below is useful for LaTeX notation:
http://en.wikibooks.org/wiki/LaTeX/Mathematics

This is the notation for a Stirling cycle number (the "first kind"). "The notation of using brackets and braces, in analogy to the binomial coefficients, was introduced in 1935 by Jovan Karamata and promoted later by Donald Knuth; it is referred to as Karamata notation" (wikipedia). "Stirling numbers of the first kind (without the qualifying adjective unsigned) are the coefficients in the expansion [to the right] where (x)(n) is the falling factorial." They "count the number of permutations of n elements with k disjoint cycles" (wikipedia). In this context, "cycle" refers to a cyclic permutation. For example, the picture below shows a cyclic permutation on 4 objects with 2 cycles. So, in this case s(4,2) = 11.
How is this related to the formula above? The formula says that the falling factorial is equal to the coefficients on a formula that looks like ax^4 + bx^3 + cx^2 + dx^1 (for n=4). So... what are a, b, c, and d? For n=4, they are:


Notice that "11" appears as the coefficient of x^2. This matches the solution for s(4,2) above. So for s(4,1) and s(4,3), we should find six distinct cycles. And for s(4,4), we should find one. Let's verify assuming we have nodes a, b, c, d.

For s(4,1) we have:
abcd
abdc
acbd
acdb
adbc
adcb

And for s(4,3) we have:
a b cd
a bc d
ab c d
cd b a
d bc a
d c ab

And for s(4,4) we only have:
a b c d

So the cyclic permutations match the coefficients on the expansion of the falling fractorial. Just to confirm that the equation above holds, let's consider it for x=5. Sure enough, it works:

The "first kind" of Sterling numbers let us expand rising and falling factorials and count cyclic permutations. Pretty neat. We'll learn about these more in 260 days or so.

Day 10: CM, Page x

Day 10. This section is called "A Note on Notation". It has a discussion of some of the notation used later in the book. Let's look at some of the interesting notation.

n¡ is a subfactorial: n!/0! - n!/1! + ... + (-1)^n * n!/n!. A subfactorial "gives the number of permutations of a sequence of n distinct values in which none of the elements occur in their original place.... In practical terms, subfactorial is the number of ways in which n persons can each give one present to one other person so that everyone receives a present" (wikipedia).

ln x: natural logarithm: log base e of x. "The mathematical constant e is the unique real number such that the function e^x has the same value as the slope of the tangent line, for all values of x." I got distracted reading about e and stumbled across Cantor's diagonal argument. I had forgotten about that from college. It's a great little observation about why the set of all sequences of 1s and 0s are not countable (i.e. there are more sequences of 1s and 0s than there are natural numbers).

s₁ = (0, 0, 0, 0, 0, 0, 0, ...)

s₂ = (1, 1, 1, 1, 1, 1, 1, ...)

s₃ = (0, 1, 0, 1, 0, 1, 0, ...)

s₄ = (1, 0, 1, 0, 1, 0, 1, ...)

s₅ = (1, 1, 0, 1, 0, 1, 1, ...)

s₆ = (0, 0, 1, 1, 0, 1, 1, ...)

s₇ = (1, 0, 0, 0, 1, 0, 0, ...)

...

s₀ = (1, 0, 1, 1, 1, 0, 1, ...)

Each sequences s1, s2, etc, above is some unique sequence of 1s and 0s. Each sequence is numbered from 1 out to infinity. s zero is constructed so that it is different from every other sequence in it's nth position. This suggests a mapping from the sequences of ones and zeros to the natural numbers cannot be constructed. For any sequence we can create and put in our list, we can create a sequence that is not in the list (s zero).

We'll get to the rest of the notation in more gory detail later. Here's a picture of Cantor:

Day 9: CM, Page ix

We have tried to produce a perfect book, but we are imperfect authors. Therefore we solicit help in correcting any mistakes that we've made. A reward of $2.56 will gratefully be paid to the first finder of any error, whether it is mathematical, historical, or typographical.
- Concrete Mathematics, p.ix

Day 9: The last page of the preface. We're almost to the real content of the book! The authors discuss the new font they developed for the book and they thank the various people who helped with the book.

Let's see how many of the people they thanked we can find on wikipedia.

1. Andrei Broder: Now a VP at Yahoo.
2. Ernst Mayr: Not on wikipedia. There is a biologist on wikipedia, but I don't think it is the same person.
3. Andrew Yao: A prominent computer scientist. Won the Knuth Prize and the Turing Award.
4. Frances Yao: Not on wikipedia.
5. Donald Zeilberger: Mathematician who won the Euler Medal (Ron Graham also won one). Here are a couple of funny quotes: "People who believe that applied math is bad math are bad mathematicians" and "Guess what? Programming is even more fun than proving, and, more importantly it gives as much, if not more, insight and understanding". And if you follow the links, the opinion pieces are funny too: "I was just kidding. They are not bad mathematicians, because they are not mathematicians at all. A true mathematician has respect for all parts of mathematics, and does not believe in arbitrary divisions into `Pure', `Applied', `Theoretical',`Practical', `Conceptual', `Computational'. Mathematics is a Web, an infinite dimensional tapestry with everything intertwined.". And "Now, Hear Yea, all you self-righteous defenders of insight and understanding. A good proof may give the appearance of understanding, but IN ORDER TO UNDERSTAND SOMETHING REALLY DEEPLY, YOU SHOULD PROGRAM IT."

That's it for the preface. Here's a picture of Donald Zeilberger.

Day 8: CM, Page viii

Research Problems may or may not be humanly solvable, but the ones presented here seem to be worth a try (without time pressure).
- Concrete Mathematics, p.viii

Day 8: Another easy preface page. On this page, the authors describe the different types of problems. The problems range in difficulty from Warmup, to Basic, to Homework, to Exam, to Bonus, to Research. It sounds like the first four categories are solvable and the last two are less solvable, with the research problems possibly not "humanly solvable". My goal is to do the Warmup, Basic, Homework, and Exam problems. I'll probably need to spend more than a day on each of those pages.

Day 7: CM, Page vii

... a concrete life preserver thrown to students sinking in a sea of abstraction.
- W. Gottschalk

Day 7: The third page of the preface. Today is another easy day. The authors describe the comments in the margins of the book. The margins contain a mix of quotations from prominent mathematicians and the students in the class. "Students always know better than their teachers, so we have asked the first students of this material to contribute their frank opinions, as "graffiti" in the margins" (CM p.vii). For example, "I have only a marginal interest in this subject". Many of the comments in the margins are humorous or corny, but many are also pragmatic and provide hints or things to watch out for.

Six more pages of preface, notation, and table of contents. Then we'll actually begin with the book!

On the side, I'm trying to get LaTeX working on my laptop. I'm going for a transparent background so I can get the blog converted back to black. Here's a test:


Hmm... the editor has a white background... I guess I'll stick to the white background.

Day 6: CM, Page vi

But what exactly is Concrete Mathematics? It is a blend of CONtinuous and disCRETE mathematics. More concretely, it is the controlled manipulation of mathematical formulas, using a collection of techniques for solving problems.
- Concrete Mathematics, page vi

Day 6: The second page of the preface. The authors explain that although Concrete Mathematics was partially a negative reaction to the new math movement, "the main reasons for its existence were positive instead of negative" (CM p.vi). One of the main goals of Concrete Mathematics is to give students a set of tools for solving real world problems.

So what do we have to look forward to? "The major topics treated in this book include sums, recurences, elementary number theory, binomial coefficients, generating functions, discrete probability, and asymptotic methods" (CM p.vi). Hey, that sounds good! But... what does it mean?

Summation

Summation is adding numbers together. Summation uses everybody's favorite mathematical symbol, the symbol on the cover of CM:


For the programmers out there, you can think of this roughly as a for loop summing numbers in an array:

for (int i = m; i <= n; i++) {            
    sum += x[i];     
} 

Here's a "concrete" example:


Often summation is more similar to summing over a function than a pre-calculated sequence of numbers in an array. This example is similar to a for loop like:

for (int k = 2; k <= 6; k++) {              
    sum += square(k);      
} 

And of course, there are many variations on the syntax above. For example, the loop boundaries may be omitted if they are clear from the context, or the loop may be over a set rather than a sequence.

Recurrences

Recurrences are recursive functions. Recursive functions include themself in their own definition.The Fibonacci Sequence is probably the most famous example:
With seeds values of 1 and 1 for n=0 and n=1, the Fibonacci Sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34,... Fractals are also often based on recurrences. The Mandlebrot fractal is one of the most famous examples.

Elementary Number Theory

According to wikipedia:

In elementary number theory, integers are studied without use of techniques from other mathematical fields. Questions of divisibility, use of the Euclidean algorithm to compute greatest common divisors, integer factorizations into prime numbers, investigation of perfect numbers and congruences belong here. Several important discoveries of this field are Fermat's little theorem, Euler's theorem, the Chinese remainder theorem and the law of quadratic reciprocity. The properties of multiplicative functions such as the Möbius function and Euler's φ function, integer sequences, factorials, and Fibonacci numbers all also fall into this area.

That all sounds familiar... but it's been a while.

Binomial Coefficients

Binomial Coefficients are so named for the binomial theorem (which we will probably return to later). They are read as "n choose k" and intuitively denote the number of ways k subsets can be chosen from a set of size n. Binomial coefficients are defined as:

To understand this formula, first start my imagining how to build unique k-sized sequences from a set of size n. You have n choices for the first element, n-1 choices for the second element, and so on down to (n - k + 1). So the probability of choosing a particular k-sized sequence is n * (n - 1) * ... * (n - k + 1). However, we are actually interested in distinct sets of elements. The same k elements in our particular sequence could also be picked in a different order and still form the same set. So how many different sequences could those k elements be picked in? k! - the number of permutations of a sequence of size k. Each of those k! sequences has an equal probability of being picked. So that particular set has a probability of being selected of k!/(n * (n - 1) * ... (n - k + 1)). Since each set has an equal opportunity of being selected, the total number of sets is the inverse of the probability of selecting a particular set, or (n * (n - 1) * (n - k + 1))/k!.

Binomial Coefficients produce many interesting patterns. For example, Pascal's Triangle is a way to calculate the binomial coefficient for any combination of n and k.

0:									1
1:								1		1
2:							1		2		1
3:						1		3		3		1
4:					1		4		6		4		1
5:				1		5		10		10		5		1
6:			1		6		15		20		15		6		1
7:		1		7		21		35		35		21		7		1
8:	1		8		28		56		70		56		28		8		1

"Row number n contains the numbers for k = 0,…,n. It is constructed by starting with ones at the outside and then always adding two adjacent numbers and writing the sum directly underneath" (wikipedia).

Within Pascal's Triangle there are also interesting patterns. For k=2, the numbers are triangular. In other words they can be drawn as a triangle. For example:

* = 1

** = 3
*

*** = 6
**
*

**** = 10
***
**
*

In the example above, the first four triangular numbers are shown: 1, 3, 6, 10. The triangular numbers can be calculated with the formula n * (n + 1) / 2. In fact, there is famous story about the mathematician, Gauss, who discovered this as a young child:

... Gauss, mathematician extrodanaire, had a lazy teacher. The “educator” wanted to keep the kids busy so he could take a nap — he asked the class to add the numbers 1 to 100 - no small feat when most kids are still learning how to carry.

Gauss walked up and showed the answer on his blackboard: 5050. The teacher thought he had cheated, but no, Gauss had figured it out by sidestepping the problem. Manual addition is for suckers, Gauss had a better way:

Sum from 1 to n =

You can understand the formula intuitively by thinking of it as a rectangle of size n and n+1 cut in half to form a triangle. This triangle, in turn, is formed of rows of size 1, 2, 3, ... n. Adding up the rows of the triangle is the same as summing from 1 to n which is the same as n(n+1)/2.

Interestingly, there is also a Triangular pattern within Pascal's Triangle for k=3. It is the sum of triangular numbers from 1 to n-2. For example, consider n=6, k=3. The binomial coefficient is 6!/3!(6-3)! = 6!/3!*3! = 6 * 5 * 4 / 3 * 2 * 1 = 120 / 6 = 20. This is also the same as the sum of the first four triangular numbers: 1 + 3 + 6 + 10 = 20. So the list of numbers in Pascal's Trinalge for k=3 and n>2 can be defined as:

Similarly, for k=4 and n>3, we have a nested summation of triangular numbers:

And for k=5 and n>4:

A pattern is starting to emerge. I'm not going to generalize on k or try to prove it for now. It's amazing that such a complicated summation can be represented by such a compact function. The results aren't something you would guess immediately, but it makes some sense if you imagine building k sized sets by iterating over an array. For k=2, you hold one pointer constant (point it at the first position) and iterate a second pointer over the rest of the elements. This forms the first row in the triangle. Next you move your first pointer to the second position. Then you iterate your second pointer over the remaining elements. This forms the second row of the triangle - it will be one element smaller than the previous row. If you repeat, it will form an entire triangle. For k=3, the pattern is similar. You hold two pointers constant and iterate a third pointer. That forms one row of a triangle. You increment your second pointer and iterate your third pointer again. This forms a second row of a triangle. You repeat until both the second and third pointers hit the end of the array. At this point, you've formed one triangle. You bump the first pointer and repeat. This begins forming a new triangle that will be one unit smaller than the previous triangle. A similar triangular pattern will be true for k=4, k=5, and so on. As you form sets by iterating over the array, each iteration creates a triangle. So all Binary Coefficients with k > 1 and k < onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://mathforum.org/dr.math/faq/pascalfib.gif">
You can even create a Sierpinski Gasket by removing odd numbers from Pascal's Triangle. For more information about Sierpinski Gaskets and Cantor Dust, check out this link.



That's all I have time for today. We'll have to save generating functions, discrete probability, and asymptotic methods for later.

Day 5: CM, Page v

The course title "Concrete Mathematics" was originally intended as an antidote to "Abstract Mathematics," since concrete classical results were rapidly being swept out of the modern mathematical curiculum by a new wave of abstract ideas popularly called the "New Math".
- Concrete Mathematics, page v

Day 5: The first page of the preface of CM. From here on out there won't be much more biographical information. We'll be getting into the meat of the book. But before that, we have a bit more honeymoon with the preface.

The first page of the preface discusses some of the changes that were happening in the educational system when the book was written in the 60s and 70s. The quote above claims that "Concrete Mathematics" was an "antidote" to "abstract mathematics" or "new math". So what's the difference between them?

According to wikipedia, pure mathematics is "motivated entirely for reasons other than application. It is distinguished by its rigour, abstraction and beauty." New math was an educational movement in the 1960s, introduced after the Spunik crisis, that attempted to provide students with a better mathematical foundation. It focused on abstract and pure mathematical concepts:

New Math emphasized mathematical structure through abstract concepts like set theory and number bases other than 10. Beginning in the early 1960s the new educational doctrine was installed, not only in the USA, but all over the developed world.... For example, in some cases pupils were taught axiomatic set theory at an early age. The idea behind this was that if the axiomatic foundations of mathematics were introduced to children, they could easily cope with the theorems of the mathematical system later.
- wikipedia

Not surprisingly, there was some backlash against new math. Parents and teachers were concerned that the material was too abstract and that children weren't learning the basics. For example, "Professor George F. Simmons wrote that the New Math produced students who had 'heard of the commutative law, but did not know the multiplication table'" (wikipedia), and Morris Kline wrote a book called "Why Johnny Can't Add: the Failure of the New Math".

Concrete Mathematics was also a part of the backlash. It eschews abstract mathematics and attempts to provide a pragmatic foundation for computer scientists and programmers.

The end-users of mathematics studies were at that time mostly in the physical sciences and engineering; and they expected manipulative skill in calculus, rather than more abstract ideas. Some compromises have since been required, given that discrete mathematics is the basic language of computing.
- wikipedia

New math is even mocked in popular culture. It was mentioned in a Simpson episode (Dog of Death) when when "Principal Skinner describes the new textbooks he'd like to use: 'History books that know how the Korean War came out… math books that don't have that base six crap in them…'" (wikipedia).



Tom Lehrer wrote a song entitle "New Math" that captures the frustration people felt. It "centered around the process of subtracting 173 from 342 in base 10 and in base 8. The song is in the style of a lecture about the general concept of subtraction in arbitrary number systems, illustrated by two simple calculations, and highlights the emphasis on insight and abstract concepts of the New Math approach."

Excerpt:

So you've got thirteen 10s and you take away seven

And that leaves five ... well, six, actually.

But the idea is the important thing.

Chorus:

Hooray for new math,

New-hoo-hoo-math,

It won't do you a bit of good to review math.

It's so simple,

So very simple,

That only a child can do it!

Concrete Mathematics was developed as an "antitode" to more abstract mathematics and the new math movement. So we can look forward to lots of pragmatic, non-abstract math! But first the rest of the preface...

Day 4: CM, Page iv

Richard M. Stallman, Linus Torvalds, and Donald E. Knuth engage in a discussion on whose impact on the computerized world was the greatest.
Stallman: "God told me I have programmed the best editor in the world!"
Torvalds: "Well, God told *me* that I have programmed the best operating system in the world!"
Knuth: "Wait, wait - I never said that."

From rec.humor.funny.
submitted by ermel@gmx.de (Erik Meltzer)

Day 4. Another easy page. The bibliographic information. Copyright '94, and '89. Nothing else too interesting, so let's take some time and get to know Knuth a little better. Here's a good link with information about Knuth. I will pull out some of the highlights, but go read the link for more. http://www.softpanorama.org/People/Knuth/index.shtml

Here is one of the earlier anecdotes about Knuth. Even when he was young, he was a problem solver:

One episode, repeated in most biographies of Knuth but still worth repeating in this one, concerns "Ziegler's Giant Bar." He entered a competition by the confectionary manufacturer Ziegler to make as many words with the letters from the phrase "Ziegler's Giant Bar" as possible. Donald spent two weeks during which he pretended to be ill and came up with 4500 words. The judges for the competition had only found 2500.

Not surprisingly, Knuth was a strong student, but had doubts about his mathematical abilities:

According to www.digitalcentury.com encyclopedia article about him: Although Knuth accomplished the highest grade point average in the history of his high school, he and his advisors had doubts as to his ability to succeed at college math. Knuth reports having something of an inferiority complex during his high school and early college years, a problem to which he attributes his over-achiever status. As a college freshman he would spend hours working extra problems in math out of fear that he would fail, only to find after a few months that his abilities far exceeded any of his colleagues.

He proved to be a strong mathematician:

Here is a relevant quote from www.digitalcentury.com encyclopedia: Knuth’s plan to become a music major changed when he was offered a physics scholarship at Case Institute of Technology (now Case Western Reserve). His turn toward math came during his sophomore year when a particularly difficult professor assigned a special problem, offering an immediate "A" in the class to any student who could solve it. Although like most of the other students, Knuth considered the problem unsolvable, he made an attempt at it one day when he found himself with some free time, having missed the bus that was taking the marching band to a performance. By what he states was "a stroke of luck," he solved the problem in short order, earned his "A," and skipped class for the rest of the semester. Although Knuth reports that he felt guilty about skipping class, he was obviously able to overcome the lost instruction because the following year he earned an "A" in abstract mathematics and was given the job of grading papers for the very course he had failed to attend.

And eventually got his PhD - he solved his thesis problem in an hour:

I got a listing from a guy at Princeton who had just computed 32 solutions to a problem that I had been looking at for a homework problem in my combinatorics class. I was riding up on the elevator with Olga Todd, one of our professors, and I said, "Mrs. Todd, I think I'm going to have a theorem in an hour. I am going to psyche out the rule that explains why there happen to be 32 of each kind." Sure enough, an hour later I had seen how to get from each solution on the first page to the solution on the second page. I showed this to Marshall Hall. He said, "Don, that's your thesis. Don't worry about this block design with =2 business. Write this up instead and get out of here." So that became my thesis. And it is a good thing, because since then only one more design with =2 has been discovered in the history of the world. I might still be working on my thesis if I had stuck to that problem. But I felt a little guilty that I had solved my Ph.D. problem in one hour, so I dressed it up with a few other chapters of stuff.

With Knuth's ability, he had a lot of options. He eventually decided he wasn't going to "optimize [his] income":

I had learned about the Burroughs 205 machine language, and it was kind of appealing to me. So I made my own proposal to Burroughs. I said, "I'll write you an ALGOL compiler for $5,000. But I can't implement all of ALGOL for this; I am just one guy. Let's leave out procedures." Well, this is a big hole in the language! Burroughs said, "No, you've got to put in procedures." I said, "Okay, I will put in procedures, but you've got to pay me $5,500." That's what happened. They paid me $5,500, which was a fairly good salary in those days. So between graduating from Case and going to Caltech, I worked on this compiler. Heading out to California, I drove 100 miles each day and then sat in a motel and wrote code. Then a startup company came to me and said, "Don, write compilers for us and we will take care of finding computers to debug them. Name your price." I said, "Oh, okay, $100,000," assuming that this was [outrageous]. The guy didn't blink. He agreed. I didn't blink either. I said, "I'm not going to do it. I just thought that was an impossible number." At that point I made the decision in my life that I wasn't going to optimize my income.

His work on compilers eventually morphed into TAOCP:

In 1962 Addison-Wesley proposed that he write a book on compiler construction. That was a much larger and much more important field that it is now. Indeed, all computer science research in those days was pretty much carved up into three parts: numerical analysis, artificial intelligence, programming languages and their compilers. The offer was accepted and lead to now famous "The Art of Computer Programming" which is definitely much more then the book on computer construction and related algorithms. He began that project in the summer of 1962 one year before graduation and being married to his wife just four months.

Here's what Knuth had to say about it:

A man from Addison-Wesley came to visit me and said "Don, we would like you to write a book about how to write compilers." I thought about it and decided "Yes, I've got this book inside of me." That day I sketched out—I still have that sheet of tablet paper—12 chapters that I thought should be in such a book. I told my new wife, Jill, "I think I'm going to write a book." Well, we had just four months of bliss, because the rest of our marriage has all been devoted to this book. We still have had happiness, but really, I wake up every morning and I still haven't finished the book. So I try to organize the rest of my life around this, as one main unifying theme.

He wrote the first volume of TAOCP by the age of 28:

[Knuth] wrote one of the most compact Algol compilers at the age of 22 and published the first volume of The Art of Computer Programming at the age of 28. His three volumes of The Art of Computer Programming played an important role in establishing and defining Computer Science as a rigorous, intellectual discipline.

After getting his PhD and finishing the first volume, he became a professor at Stanford. He already had a reputation:

Even among computer pioneers in Stanford, Donald Knuth was considered to be almost legendary figure. The following old anecdote from Alan Kay, one of the principal designers of the Smalltalk language, illustrates the point: When I was at Stanford with the AI project [in the late 1960s] one of the things we used to do every Thanksgiving is have a computer programming contest with people on research projects in the Bay area. The prize I think was a turkey. [John] McCarthy used to make up the problems. The one year that Knuth entered this, he won both the fastest time getting the program running and he also won the fastest execution of the algorithm. He did it on the worst system with remote batch called the Wilbur system. And he basically beat the shit out of everyone. And they asked him, "How could you possibly do this?" And he answered, "When I learned to program, you were lucky if you got five minutes with the machine a day. If you wanted to get the program going, it just had to be written right. So people just learned to program like it was carving stone. You sort of have to sidle up to it. That's how I learned to program."

Knuth finished the second and third volume of TAOCP as well as creating the TeX typesetting language. And of course he has done many other things:

He really has managed to make contributions to a very wide area of computer science topics. Among them:
- Suggested the name "Backus-Naur Form"
- Wrote one of first and one of the most compact Algol compilers;
- Designed the SOL simulation language;
- Designed and wrote the TeX and Metafont systems of documentation (written in WEB for Pascal);
- Introduced and refined the LR parsing algorithm (see Knuth, D.E. 1965. "On the Translation of Languages from Left to Right", Information and Control, Vol. 8, pp. 607-639. The first paper on LR parsing.)
- Invented several important algorithms including Knuth-Morris-Pratt string-searching algorithm;
- Made the crucial contribution to the "Structured programming without GOTO" programming debate, which was a decisive blow to the structured programming fundamentalists led by E. Dijkstra;
- Published his groundbreaking paper "An empirical study of FORTRAN programs." ( Software---Practice and Experience, vol 1, pages 105-133, 1971) which laid the cornerstone of an empirical study of programming languages.
- Made the crucial contribution to dispelling "correctness proof" mythology.

But the TAOCP is his masterpiece:

Still no other book in CS can be compared with his encyclopedic The Art of Computer Programming (TAoCP). It is one of the few books that remain largely relevant 30 years after the initial publication. I am convinced that every person who suspects that he/she has a programming abilities (and BTW an early start is a good indication of abilities in any field, including programming) should buy or borrow the first volume of TAoCP and try to solve exercises after each chapter. The ability to solve difficult exercises form the first volume is a sure sign of people with substantial talent and can be a good self-test if you it make sense to dedicate yourself to carrier in computer science or not.

He is continuing to work on the forth volume. Hopefully, he will finish it soon (there are rumors of 2008). But he admits he may not be able to finish his original ambitious plan:

His primary agenda item is, after all, Volume 4, although every few months he’ll browse journals for items to squirrel away for Volumes 5 through 7. People inquire delicately about how he expects to complete a seven-volume project at his current pace, and Knuth concedes he’ll be content to finish the first five.

How do your gain expertise in something?

By studying the masters and not their pupils. Abel, Niels H. (1802 - 1829)

So let's get started studying the master!