Unit 4 · Algorithms & Simulation · Lesson 4.1

What Counts as an Algorithm

Three ways to find a word in a dictionary. All correct, all algorithms, only one fast. Today: what makes something an algorithm — and the first hint that correct isn’t the same as good.

Big Idea 3 — Algorithms & ProgrammingUnit 4 opener · no new syntax

Before this lesson — read on Runestone

19.1 Computer Abilities Summary — what a computer can actually do, in one page

This is the only Runestone reading for Unit 4. The book doesn’t cover search, efficiency, or simulation — from 4.2 on, these lesson pages are the reading. Enrolled in our Runestone course? Open it from there so your progress counts.

Where We Are

People→ Bits→ Programs→ Internet→ Security→ Big Data→ Impact

A new unit, but you haven’t left Programs. Unit 4 builds the Algorithms region of the map — the bridge between the programs you write and the bits they run on. No new syntax this unit. Every tool is from Unit 3; you’re about to find out which uses of those tools are good.

The Hook

Find the word “quokka” in a dictionary. Three students describe how they’d do it:

1. Start on page 1 and read every word until you hit it.

2. Flip to the Q section, then go page by page.

3. Open to the middle. Is “quokka” before or after this page? Throw away the wrong half. Repeat.

All three are correct. All three are algorithms. Only one of them is fast — and by the end of this week you’ll be able to say exactly how much faster, with a number you produced yourself.

The Idea

An algorithm is a finite set of instructions that accomplishes a specific task. That’s it — no computer required. A recipe is an algorithm. So are directions to a friend’s house. And every algorithm you will ever write is built from just three pieces, the same three you’ve been using since Unit 2:

Building block	What it means	You first met it
sequencing	Steps run in order, one after another	2.1 — your first program
selection	A condition decides which steps run	2.12 — if / else
iteration	Steps repeat	3.1 — the while loop

Different algorithms can solve the same problem. In 3.9 you found the largest value in a list by keeping a running “biggest so far.” Here’s a completely different algorithm for the same job: for each value, check it against every value — if nothing beats it, it’s the max.

Python — Algorithm B, the challenger

def biggest_b(nums):
    for x in nums:
        is_max = True
        for y in nums:
            if y > x:
                is_max = False
        if is_max:
            return x

AP Pseudocode

PROCEDURE biggestB(nums)
{ FOR EACH x IN nums
  { isMax ← true
    FOR EACH y IN nums
    { IF (y > x)
      { isMax ← false } }
    IF (isMax)
    { RETURN (x) } } }

Hover or tap a line to light its twin. Find all three building blocks: the lines run in order (sequencing), the IFs choose (selection), the FOR EACHes repeat (iteration). Algorithm B is correct. The question is whether it’s good.

Try It — Same Answer, Different Work

Algorithm A is your 3.9 max: one pass, keep the biggest. Algorithm B is the challenger above. Both count every > comparison they make. Change the list and watch the two numbers.

list:

Presets:

Try the 20-item preset. Both algorithms agree on the answer — so which is “better”? Notice you can say B did more comparisons, but not yet how much worse B gets as the list grows. That missing vocabulary is what this week is for.

Vocabulary

algorithm Programs: A finite set of instructions that accomplishes a specific task.
sequencing Programs: Running steps in the order they are written.
selection Programs: Using a condition to decide which steps run.
iteration Programs: Repeating steps a set number of times or until a condition is met.

All four are review. Today they become the definition of the thing this whole unit is about.

Check

Five questions. One is a REPEAT UNTIL trace — the flips don’t take a holiday.

0 of 5 answered

Impact Check

Correct isn’t the only thing that matters

An organ-donor matching system has to compare every patient on a waiting list against every new donor. Two algorithms both produce correct matches. One finishes in seconds. The other finishes in days — and a donated organ lasts hours.

When an algorithm runs on real people’s time, “it gets the right answer eventually” can still be the wrong algorithm. That’s why the rest of this unit measures how much work, not just whether it works.

Connections

Came from 3.9 — Algorithm A is your max algorithm. Now it has a rival.

Next in 4.2 — algorithms combine: build a new one out of procedures you already own.

Returns in 4.5–4.6 — the vocabulary for “better” that you were missing today: how work grows as the list grows.

Returns on the exam — “which of these algorithms accomplishes the task?” often has two correct answers. Correct and efficient are different questions.