Quirksand

SICP

SICP 1.2.3 Solutions

August 30, 2012 19:44

Ex 1.14

The first part, the graph, is fairly easy to produce, if a bit tedious. Simply go through each part of the procedure and add to the tree whenever there is a new call to cc. Naturally I did this by hand on paper first, but I’ve provided a more readable version below.

cc procedure call tree

It’s the second part of the question that gets complicated. Figuring out the order of an algorithm, even a relatively straightforward one like the change-counting one seen here, takes a fair amount of insight; proving it is an even tougher task. Even here, where I’m going to go on at some length, I won’t be fully proving it. What I will provide will hopefully be convincing enough, and as I haven’t seen this approach before might help understanding the problem in a different way.

In the following, I’m using n for the amount and k for the number of coin types. For practical purposes, the amount is likely to be more than the number of coin denominations, so it’s assumed that n > k . One reason why Big-O is used so often that I didn’t get into last time is that it can help reduce the number of variables it’s necessary to consider. Usually there is only one critical value to use in comparing algorithms, ideally in simple expressions. Using Big-O can avoid the need to include what might be distracting variables, since often the behavior when only that critical value increases is what’s important. Our n is the most important value here, as it’s the one likely to grow large.

The order in space actually isn’t too hard to figure. Each call takes up its own space, and spawns at most two branches. Each branch increases the depth of the tree while reducing the amount n , and may also add a branch while reducing k. Considering that n is the most important value, it will be the depth of the tree in that direction that matters most for space concerns. Since reducing the amount by 1 increases the depth by 1, the depth grows linearly with n. Thus the order in space is O(n).

For time, we can say that each call to cc takes roughly the same amount of time; there is very little calculation involved otherwise. If addition were expensive, this might be different, but for numbers it really isn’t. We’ll assume it’s the number of procedure calls that determine the order in time.

As I mentioned I won’t do a general proof. Instead I’m going to show it for a specific subset of the problem, and suggest that it applies to all other versions as well.

Imagine a ‘worst-case’ run of the procedure, in which all possible coins are considered as change, and we run through all values from n down to 0.

Such a run can be generated using a degenerate set of currencies, which all have a denomination of 1. Any n of them in various combinations will be a valid change set, and when computing them only 1 will be taken off the amount at each branch.

The solution to this version can be calculated without using the procedure. Let any valid change combination be expressed as a sequence by using two symbols. The symbol ‘*’ indicates one coin, and ‘_’ means switch to the next coin type. For instance, if there are three denominations, ‘**_*****_*’ would mean 2 of denomination 1, 5 of denomination 2, and 1 of denomination 3, summing to 8. In these expressions the sequence is always of length n + k – 1, and there will always be n * symbols. This result can be calculated directly as C(n + k- 1, n) , with C as the choose function . (Another name for this problem is “combinations with repetition”).

But what we really want to know is how many times the procedure would be called if we did use it to solve the problem. If you look at the call tree above, you may notice a few similar sections (at some point cc gets called with the same values down different branches). Since in this simplified version all our coins have the same value, the tree will have a lot of duplicated nodes. Written out, they could be overlapped without a problem. There’s a diagram of what it looks like below for n = 5 and k= 4. The middle nodes will actually be called multiple times; some from the node to its upper left, and some from the node to its upper right. The number of times a node is called is indicated in red above the node (the nodes on the top edges are only called once). Eventually the calls will end up either on the lower right side, with amount = 0 (allowable change), or on the lower left, with kinds-of-coins = 0 (no change). These nodes, it may be noted, are only connected to one other node so will be called the same number of times as the node they’re connected to.

call tree with repeated nodes

Since the number of times each interior node is called is the sum of the two nodes above it, and the outside edges are all 1, what we have in the middle is a portion of Pascal’s Triangle. We can use the properties of Pascal’s Triangle to help figure out how many procedure calls in total there are.

For one, any entry in Pascal’s Triangle can be calculated from the row and offset into the row using the choose function: it is simply C(row, offset). Another property, very useful for us, is what’s called the ‘Hockey Stick Rule’, due to the shape it describes. If you wish to know the sum of any diagonal of numbers extending from the edge to somewhere in the middle of the Triangle, it is the number just below and in the opposite direction of the diagonal. Expressed using the binomial coefficients (i.e. the choose function expressions), the result is:

m-1 C(r+i,i) = C(r+m,m-1)
Σ
i=0

In that expression, r is the row the diagonal starts on, and m is its length. Note that we start our row and offset indexing at 0 when using these formulas.

We’ll split the total calls into two types — those that terminate and return a single value, and those that do not immediately terminate and rely on the calls below them in the tree.

The calls that do not immediately terminate form the parallelogram-shaped portion of Pascal’s Triangle. Each row along one edge is a diagonal that sums to the value at the end of the row just below it. This means that these sums themselves form a diagonal, or at least nearly one, made up of the values at the ends of the rows, plus one more value further into the interior. The outer value ‘1’ is missing in this diagonal. For the moment, we’ll ignore that and just consider the whole line. Using the Hockey Stick Rule again, it sums to the value just below and in the other direction from that diagonal. This leads to the entry straight down from the bottom tip of the parallelogram (two rows below it).

If we sum our rows along the n – length side of the parallelogram, our final diagonal starts on row n – 1. There will be k + 1 steps, one for each row plus the extra one to complete the diagonal. The formula gives us the value for this sum as C(n + k, k). We can use the fact that for the choose function C(a, b) = C(a, a-b) and rewrite the result as C(n + k, n) .

Next there are the terminating calls. The successes (i.e. valid change combinations) will come from calls at the lower right edge, and there will be just one for each call to its upper left. This just copies the bottom diagonal of the parallelogram. Similarly, all the calls that end on the lower left (failures) will occur once for each call on its upper right. The total number of terminating calls will be the value one below and to the left of the parallelogram (for failures), and one below and to the right of the parallelogram (for successes).

Those two values are in fact in the Triangle just above the sum we figured for non-terminating calls. That means the number of successes and the number of failures sum to that same number. A diagram of how these sums come about for the values already considered is shown below. The orange lines show nonterminating cases, the purple show failures, and the blue show successes.

summing the calls

The total number of calls, then, is twice that number. Although we have to remember to subtract the 1 we ignored earlier.

Total procedure calls: 2 * C(n + k , n) – 1

As a quick check, we can also compute the total number of successes, which is the answer to our routine, using the Hockey Stick Rule. The starting row for successes is n – 1, and there are k of them. The formula gives the result C(n + k – 1, k – 1) which again can be rewritten as C(n + k – 1, n) . This matches the value as figured previously.

It’s important to remember that I have only shown this to be valid for this particular subset of the original procedure. I have claimed (without proof) that this is a “worst-case” class of the problem. A procedure with unique positive integer values for currencies will take a number of steps that are some fraction of this value. If fractional coin values were possible, the values could be normalized without changing the amount of time taken. The claim, then, is that if this case is O(f) then all sets of coins will complete in O(f) time.

A simpler bound more useful for comparisons can be derived by breaking down the expression another way. This is derived from the definition of the choose function, and by reducing some of the terms in the factorial expression.

C(n + k , n) = ( n + k )!
n! k!
C(n + k , n) = ( n + k ) * ( n + k – 1) * ( n + k – 2) * … * ( n + 1)
k!
The number of calls is:
−1 + 2 * ( n + k ) * ( n + k – 1) * ( n + k – 3) * … * ( n + 1)
k !

The growth of this is determined by the fraction’s numerator, which will be a polynomial in n having n k as its highest term. The time taken increases at a rate no worse than n k. Written using Big-O notation, the time taken for the procedure is O( n k).

I did write some routines to try and test this. It’s obviously impossible to empirically prove something true for all values, and it certainly doesn’t give the exact bound of the result. Instead, it serves as a sanity check on our result. If something wildly different from that expected shows up, then something is wrong about the result (or the testing method, perhaps).

The test procedure makes use of the display routine which hasn’t been encountered in the book, although it will show up soon enough. It’s simply used to output something to the screen. newline, as might be expected, ends the output line. An altered version of cc, cc-counter, performs almost the same calculation as cc but instead returns the total number of times it is called, by simply returning or adding 1 in all cases.

The critical part of the test procedure is determining the call count compared to n k. If the procedure were exactly on the order, then this ratio would be constant. As it is, we only expect O( n k), meaning that it should do no worse than this. And if it stays roughly in the range, then our calculation is a good estimate. My tests show that with the same value of k, the fraction does stay pretty close; at least in a narrow range and apparently decreasing with higher n, which is a good sign. Changing k seems to change the constant again, though also with a decrease. This suggests that, for this version of the problem at least, the number of calls has some other dependence on k but likely does not grow faster than nk, which is what we expected. It should be noted that this is still just a measure of the number of calls, not the real time taken in the procedure.

Ex 1.15

There are a couple ways to determine the answer to this problem. One way is to work it by hand. Not too many steps are required, so it’s not too onerous. A better version of that is to use a debugger to step through the procedure. This does much of the same work, but with the advantage of no inadvertent mistakes that result in a wrong answer. The procedure is given to us, so we simply have to follow it.

I’ve done it another way, making use of the display procedure to show the answer. Each time p is called, it prints out a line. Counting those lines gives the answer. Normally this isn’t a great way to accomplish this task (for one, it changes the routine as given to us so is in a sense incorrect; our p is not the original p but common sense says the number of calls is the same). This method is easier to repeat in a file, though, and takes less time. There do exist debugging tools that would count the calls to a procedure without requiring you to rewrite it, which would probably be the best way to handle it if doing this computationally, quickly, and repeatably is desired, though some time must be invested learning to use them.

The second part of the problem in this case is much simpler than in 1.14. For one, this is a straightforward recursion, with the number of calls to sine being the primary factor in both the space and time required. Both of them can be found by figuring the number of calls needed.

Repeatedly dividing by 3 means that we are expecting the value for angle a to be 0.1*3x, with x an unknown value. To make this a little more generic, let’s replace the value 0.1 with ε, the understanding being that it is a nonzero positive value small enough to allow for termination. It should be clear that ceiling(x) (the closest integer >= x) is the number of divisions required before the value is less than ε. We need to figure out what x is, then.

a = ε * 3x
log3a = log3(ε * 3x)
log3a = log3ε + log3 3x
log3a – log3ε = x
log3 (a/ ε) = x

The ceiling of this result gives us the order in time and space required.

To check this (and as yet another way to solve part a), we can answer the first question asked using the numbers given. To figure the calls required for sin(12.15) with ε = 0.1, we have log3(12.15/0.1) = 4.369; the next integer is 5, which is the right answer.

Since ε is a fixed value and not a variable, it will not affect a practical consideration of the order of growth to ignore it. Similarly, if we only concern ourselves with orders, the base of the logarithm makes no difference either. In this case we can simply express the time and space as being O(log a) .

Solutions 1.2.3