1.1. The Model¶

Recall that to do analysis, we have to define a model with two parts: a definition for the size of the input, and a definition for how to measure the cost of a solution.

1. The size of the input is the number of disks.
2. The cost of the solution is the number of moves made.

1.2. Finding an Algorithm¶

When trying to solve most problems, a good place to start is to try to solve it for small instances. How would we solve the problem when there are 0 disks, 1 disk, 2 disks, and so on? Those should all be pretty easy for you to figure out. How about 3 disks? This starts to get a bit harder. Think about all the possible choices for a 3-disk series of moves. There a several possibilities, but you should find that there is only one "reasonable" one. Can we generalize the insight from solving for 3 disks? How about when we solve for 4 disks?

Here is a useful observation: The largest disk has no effect on the movements of the other disks. Why? Because it is always below the other disks, so they can move around as though it did not exist. Why is this useful? Because it essentially means that we can ignore the biggest disk when we think about solving subproblems. Most importantly, it means that we can use the pole that the biggest disk is sitting on to solve the subproblems, just as if that disk was not there at all.

Here is another observation that you should come to, if you actually play around with the problem yourself. This one is critical: We can't move the bottom disk from Pole A to Pole B unless all other disks are already on Pole C. This critical observation almost immediately gives us a solution to the problem.

Problem solving often relies on a "key insight" that lets you "crack" the problem. Similarly, analysis of the problem might rely on a "key insight" on how to view the analysis. This is often a simplification for the "states" or progess of the algorithm, or a recognition of the key input classes for the problem.

When we generalize the problem to more disks, we must end up with a process something like:

• Move all but the bottom disk to Pole C.
• Move the bottom disk from Pole A to Pole B.
• Move the remaining disks from Pole C to Pole B.

Notice that in this discussion, we used a number of problem-solving heuristics to solve this problem, including:

• Get our hands dirty: Try playing with some simple examples
• Go to the extremes: Check the small cases first
• Penultimate step: Key insight is that we can't solve the problem until we move the bottom disk. So to solve the whole problem, we first clear off the bottom disk, then we move the bottom disk, then we solve the rest of the problem. Reducing the full problem to these pieces is hopefully easier to solve than the original problem was.

As a practical matter, how do we deal with the fact that we have to move \(n-1\) disks (twice)? As programmers, we are used to packaging tasks into subroutines of some sort. In this case, since solving the problem on \(n-1\) disks looks just like a smaller version of solving the original problem, it seems natural to use recursion.

Generalizing the problem-solving approach a bit, we can say that we used a forward-backward strategy: First we solved simple special cases and generalized their solution, then we tested the generalization on other special cases.

Here is the algorithm, cast as a program:

void Tower1(int n, POLE start, POLE goal, POLE tmp) {
  if (n == 0) return;             // Base case
  Tower1(n-1, start, tmp, goal); // Recurse: n-1 disk
  move(start, goal);              // Move one disk
  Tower1(n-1, tmp, goal, start); // Recurse: n-1 disk
}

1.3. Analysis of the Algorithm¶

Since the input to the problem is the number of disks, and the size of the problem is also the number of disks, there is only one input instance of size \(n\). So we do not need to worry about complicating issues related to whether we are concerned with the worst, best, or average case costs. This is one of the reasons why we picked this problem to discuss first—we don't have the complexity of a range of inputs for a given size \(n\).

Given an algorithm to solve the problem, we want to know what the cost of that algorithm is as a function of the input size. In particular, we want to know the growth rate for the algorithm as the input size grows. In particular, our cost model says that our cost is the number of moves that are made to solve the problem. So, we want to count the number of moves required as a function of \(n\).

To do this, we will need a mathematical model, some equation that defines the number of moves as a function of \(n\). How do we get there? We can either deduce this from the structure of the algorithm, or by observing its behavior. Let's start with behavior (though with a bit of proficiency we will find that the structure of this particular algorithm makes the equation fairly straightforward). Here are some facts to get us started, by counting the number of moves that the algorithm makes for some small inputs.

• \(f(0) = 0\).
• \(f(1) = 1\).
• \(f(2) = 3\).
• \(f(3) = 7\).

Now, how do we generalize this? If we look at the algorithm, we see that there are two recursive calls, and one move is made. We don't know what the cost of a recursive call actually is. But if we give a name to the cost of our algorithm, then we can use that same name to identify the cost of the subproblem. So, for an arbitrary input size of \(n\), we can generalize the cost as:

• \(f(n) = f(n-1) + 1 + f(n-1) = 2f(n-1) + 1, \forall n \geq 4\).

This is using a recurrence relation, and we will need to "solve" it by finding a closed-form solution for the recurrence.

Actually, we can simplify our list of facts. We only need f(1) and f(n), facts f(2) and f(3) are redundant information. But spelling them out might help us to see the pattern. We only need one base case in this case. So here is the formal recurrence relation that defines the mathematical model for our algorithm's cost:

How can we find a closed-form solution for this recurrence? Normally, we can't get anywhere with one of these analysis problems until we "get our hands dirty" with some small examples of the behavior of the equation. So here is a small table with the first few values.

Can we see a pattern here? It looks like each time we add a disk, we roughly double the cost—something like \(2^n\). If we examine some simple cases, we see that they appear to fit the exact equation \(f(n) = 2^n - 1\).

This really is a common way to go about figuring out the closed-form solution for many recurrence relations and summation: Look at what happens, try to find (or guess) a pattern, and then test the pattern. This is so common that it has its own name: Guess and Test. We will use this a lot to help us with analysis.

Now that we have a pretty good guess, how do we prove that this always works? This is the "test" part of "guess and test".

Let's assume that \(f(n-1) = 2^{n-1} - 1\), and see what happens. Take the recurrence, and simply replace \(f(n-1)\) with our guess that it is \(2^{n-1} - 1\). Doing this gives us \(f(n) = 2f(n-1) + 1 = 2(2^{n-1} - 1) + 1 = 2^n - 1\).

The implication here is that if there is ever an \(n\) for which \(f(n) = 2^n - 1\), then for all greater values of \(n\), \(f\) conforms to this rule. This is the essence of proof by induction. To prove by induction, we need to show two things:

1. We can get started (base case).
2. Being true for \(k\) implies that it is true also for \(k+1\).

Here is the complete induction proof for Tower1:

1.4. Lower Bound for the Problem¶

Is this a good algorithm? That would depend on what? On the intrinsic difficulty of the problem!

To decide if the algorithm is good, we need a lower bound on the cost of the PROBLEM. The lower bound for the problem is the tightest (highest) lower bound that we can prove for all possible algorithms that solve the problem. This can be a difficult bar, given that we cannot possibly know all algorithms for any problem, because there are theoretically an infinite number.

Lower bounds don't give you a good algorithm. They only help you know when to stop looking. If the lower bound for the problem matches the upper bound for the algorithm (within a constant factor), then we know that we can find an algorithm that is better only by a constant factor.

Can a lower bound tell us if an algorithm is NOT optimal? No, sorry! Why not? Because we might not have the tightest possible lower bound!

Let's determine the lower bounds for Towers of Hanoi. Another reason why we picked this problem to start with is because it is "obvious" what the lower bound cost to the problem is. So now we can focus entirely on the technique of proving the math, not figuring out what to analyze.

For our first try at a lower bounds proof, the "trivial" lower bound is that we must move every disk at least once, for a minimum cost of \(n\). Slightly better is to observe that to get the bottom disk to the third pole, we must move every other disk at least twice (once to get them off the bottom disk, and once to get them over to the third pole). This yields a cost of \(2n - 1\), which still is not a good match for our algorithm. Is the problem in the algorithm or in the lower bound?

We can get to the correct lower bound by the following reasoning: To move the biggest disk from first to the last pole, we must first have all of the other \(n-1\) disks out of the way, and the only way to do that is to move them all to the middle pole (for a cost of at least \(\textbf{T}(n-1)\)). We then must move the bottom disk (for a cost of at least one). After that, we must move the \(n-1\) remaining disks from the middle pole to the third pole (for a cost of at least \(\textbf{T}(n-1)\)). Thus, no possible algorithm can solve the problem in less than \(2^n-1\) steps. Thus, our algorithm is optimal.

1.5. New Models¶

New model #1: We can move a stack of disks in one move. This is a big help! \(O(n)\) or even \(O(1)\).

New model #2: Not all disks start on Pole A. This doesn't seem to change the cost of the problem. (Why?)

Combining these two things, the cost looks to be \(O(n)\).

New model #3: Different numbers of poles.

New model #4: We want to know what the \(k\) th move is.

1.6. Putting it all Together¶

So now we have an answer to the question "How do I know if I have a good algorithm to solve a problem?" An algorithm is good (asymptotically speaking) if its upper bound matches the problem's lower bound. If they match, then we know to stop trying to find an (asymptotically) faster algorithm. What if the (known) upper bound for our algorithm does not match the (known) lower bound for the problem? In this case, we might not know what to do. Is our upper bound flawed, and the algorithm is really faster than we can prove? Is our lower bound weak, and the true lower bound for the problem is greater? Or is our algorithm simply not the best?

Now we know precisely what we are aiming for when designing an algorithm: We want to find an algorithm who's upper bound matches the lower bound of the problem. Putting together all that we know so far about algorithms, we can organize our thinking into the following "algorithm for designing algorithms". [1]

We can repeat this process until we are either satisfied or exhausted.

This brings us smack up against one of the toughest tasks in analysis. Lower bounds proofs are notoriously difficult to construct. The problem is coming up with arguments that truly cover all of the things that any algorithm possibly could do. The most common fallacy is to argue from the point of view of what some good algorithm actually does do, and claim that any algorithm must do the same. This simply is not true, and any lower bounds proof that refers to specific behavior that must take place should be viewed with some suspicion.

Which brings us back to the argument that we used to justify our lower bound for Towers of Hanoi. This is essentially an argument about necessary behavior. Towers of Hanoi is rather rare in that we do have some specific behavior that we know must happen. In this particular case the problem is so constrained that there really is no (better) alternative to this particular sequence of events. This approach will not work for most problems.

Does our "problem solving algorithm" always terminate? No. You might get stuck in a loop if you go through and make no progress. So, is it an algorithm?