A First Taste of Algorithms

Lab 1: Counting Steps

✦ ✦ ✦

Accompanies Chapter 1. The chapter asked two questions of every algorithm: does it give the right answer, and what does the answer cost? This lab is about measuring cost — not with a stopwatch, but by counting.

1. Looking through a list is a loop

Chapter 1’s first algorithm was the obvious one: to find a name in an unsorted list, check the first entry, then the second, and keep going until you find it or run out. Written in Python, the algorithm and the sentence describing it are nearly the same thing:

names = ["Ada", "Erdos", "Gauss", "Hua", "Noether", "Ramanujan"]

for name in names:
    if name == "Hua":
        print("found it")

The new construct is the for loop. The line for name in names: means: take each entry of the list in turn, call it name, and run the indented lines below for it. The loop is not a programming trick bolted onto the algorithm. The loop is the algorithm — “check each one in turn” — written in a notation the machine accepts. (The other new construct, if, does what it says: run the indented line only when the condition holds. It will earn a fuller treatment in Chapter 2, where an algorithm’s whole character turns on a single if.)

2. Make the cost visible

The program above finds Hua but keeps its effort secret. Add the counter from Lab 0:

names = ["Ada", "Erdos", "Gauss", "Hua", "Noether", "Ramanujan"]

steps = 0
for name in names:
    steps = steps + 1
    if name == "Hua":
        print("found after", steps, "steps")
        break

(break means: stop the loop now. Without it, the loop would keep checking names after finding Hua — correct, but wasteful, and we are in the business of counting waste.)

Run it. Then move "Hua" to the front of the list and run it again. Then to the back. Three runs, three costs. The cost of this algorithm is not a number; it depends on where the target sits. When we say linear search takes up to n steps on a list of n items, the “up to” is doing honest work — it is the worst case, the only promise the algorithm can keep no matter where the target hides.

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