A First Taste of Algorithms · Lab 0: Talking to the Machine

4. The machine tells you when you’ve lost it

Run this. It is broken on purpose.

print("the answer is " + 42)

Python stops and prints several lines of complaint ending in something like:

TypeError: can only concatenate str (not "int") to str

Read the last line. It is not scolding you; it is reporting, precisely, what it could not do: glue a piece of text to a number, because those are different kinds of things. An error message is information. Every programmer who has ever lived reads dozens of them a day. The ones who get good are the ones who read them rather than flinch.

Fix the program by making the number into text:

print("the answer is " + str(42))

5. The machine is fast

One more, and this one needs a construct we will not explain until Chapter 1 — run it anyway:

total = 0
for n in range(1, 1000001):
    total = total + n
print(total)

This adds every whole number from 1 to one million. Run it and notice two things. First, the answer appears before your finger leaves the key. A million additions cost the machine nothing you can perceive. Second — check the answer. Gauss, as a schoolboy, is said to have computed this sum (to one hundred, but the trick scales) in seconds, by thinking instead of adding: pair 1 with 1,000,000, pair 2 with 999,999, and so on; 500,000 pairs, each summing to 1,000,001.

So there are two ways to be fast: do the dumb thing very quickly, or find a way to not do most of the work at all. The machine gives you the first for free. This book is about the second. An algorithm is, more than anything else, a way of not doing most of the work — and the strange, wonderful fact is that the not-doing can be written down, studied, and proved correct, like any other piece of mathematics.

That is where Chapter 1 begins.

Break it

End every lab this way: change one thing, predict what will happen before you run it, run it, and if the prediction was wrong, figure out why. The prediction is the exercise. Running the code only grades it.

1. In §3, swap the last two lines, so print(steps) comes before the second steps = steps + 1. What prints?
2. In §5, change range(1, 1000001) to range(1000001). Predict whether the answer changes, then check. (Something here starts at 0. Does it matter?)
3. In §5, change one million to one billion: range(1, 1000000001). Predict first: instant, a few seconds, a minute, or never finishes? Then run it and time it. You have just taken your first measurement of the thing this whole book is about — what computation costs.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses