Reference Guide

Key Topics

Term Definition Example
Algorithm A finite set of instructions that accomplish a specific task. Adding up Safe Nights donations and checking the goal.
Sequencing Running steps in order. Set total = 0, then add, then print.
Selection Choosing what to do with an if. if total >= goal:
Iteration Repeating steps with a loop. for amount in donations:
Equivalent algorithms Same result and same side effects, for every input. Two different seat checks that always agree.
Side effect A change besides the returned result. .sort() reorders the original list.
Boundary input The value exactly at a limit, where < and <= disagree. A workshop with exactly 12 of 12 seats filled.
Modify / Combine Change a known algorithm / use two algorithms together. Turn a counter into a collector.

Python Algorithm Tools

Tool Meaning Example Notes
Counter Counts how many items match. count = count + 1 Starts at 0.
Running total Adds values as you go. total = total + amount Starts at 0.
Collector Builds a list of matching items. names.append(name) Starts as [].
Max finder Tracks the largest value seen. if x > largest: largest = x Start at the first item.
Comparison Decides pass or fail at a limit. if signed_up >= 12: Check > vs >= at the boundary.
Function Packages an algorithm to reuse and test. def has_seat(signed_up): Test it with several inputs.

College Board Pseudocode Connections

College Board pseudocode Python connection Python example When to use it
total ← 0 total = 0 total = 0 Store or update a value.
DISPLAY(total) print(total) print("Total:", total) Show a result.
IF (condition) { } if condition: if amount >= 100: Choose between paths.
FOR EACH item IN list { } for item in list: for amount in donations: Visit every item in a list.
APPEND(list, value) list.append(value) names.append(name) Add to the end of a list.
LENGTH(list) len(list) len(donations) Count the items.
list[1] is the first item list[0] is the first item donations[0] Pseudocode indexes start at 1, Python at 0.

The algorithm is the same idea in both: what repeats, what gets checked, and which variables change. The Popcorn Hacks run right on this page. You’ll copy them into your own notebook afterward (section 6).


Lesson Plan

Learning targets: I can (1) name the three building blocks of every algorithm, (2) test whether two algorithms are equivalent, and (3) build a new algorithm from patterns I already know.

Success criteria: I predict a loop’s output before running it; I test inputs below, at, and above a limit; my homework matches the expected output and has a comment on every block.

Why: Our capstone site is built from small algorithms: add up donations, check whether a workshop is full. When one is almost right, nothing crashes. The site just shows the wrong number. This is also exactly what 3.9 tests on the AP exam.

Rules: Predict before you run. Comment every block you write. Test the edges.

Time What happens Students do
0-1 min Tech Talk hook Listen
1-3 min Participation 1: Human Robot One volunteer acts it out, class gives instructions
3-7 min Part 1: What is an algorithm? Run Example A → Popcorn 1
7-11 min Part 2: Same result, or not? Predict Example C → Popcorn 2
11-13 min Participation 2: Table Talk Discuss 1 min, a volunteer answers
13-16 min Part 3: Modify and combine Popcorn 3
16-18 min Participation 3: Fastest Table First table with a correct answer shouts it out
18-20 min MCQ + homework preview Start the MCQ (finish at home if needed)

Tech Talk: Two algorithms can look completely different and do the same thing. Two can look almost identical and do different things. Today you’ll learn to tell which is which by testing, not guessing.

College Board Requirements

Big Idea 3, Algorithms and Programming (30-35% of the AP exam), Topic 3.9 Developing Algorithms.

AAP-2.L: Compare algorithms. Decide whether algorithms produce the same result and the same side effects.

  • AAP-2.L.1 “Algorithms can be written in different ways and still accomplish the same tasks.”
  • AAP-2.L.2 “Algorithms that appear similar can yield different side effects or results.”
  • The same objective says a conditional can be rewritten as an equivalent Boolean expression, and the reverse.

AAP-2.M: Create algorithms. “For algorithms: a. Create algorithms. b. Combine and modify existing algorithms.”

  • AAP-2.M.1 “Algorithms can be created from an idea, by combining existing algorithms, or by modifying existing algorithms.”
  • College Board lists existing algorithms to know, including sum/average and maximum/minimum, and notes that reusing correct algorithms saves time and makes errors easier to find.
Requirement Where
Algorithms in pseudocode and Python Participation 1, Part 1, Popcorn 1
AAP-2.L.1 + conditional ↔ Boolean expression Part 2, Example B, Participation 2
AAP-2.L.2 different result / side effect Part 2, Popcorn 2, MCQ
AAP-2.M create, combine, modify Part 3, Popcorn 3, Participation 3, Homework

The Lesson

Python (main) · College Board pseudocode (sub)

Every example here comes from a community nonprofit project, Safe Passage Heals, which supports survivors of trafficking and domestic violence in San Diego through counseling, workshops, and its Safe Nights campaign. We only use its day-to-day operations (donations, workshop seats, volunteer hours, supplies), never anyone’s personal information.

Part 1: What Is an Algorithm?

An algorithm is a finite set of instructions that accomplish a specific task, like “add up tonight’s donations and check whether we hit the $500 Safe Nights goal.” Every algorithm, in any language, uses three building blocks: sequencing (steps in order), selection (if), and iteration (loops).

flowchart TD A["donations list, goal = 500, total = 0"] --> B{"More donations to add?"} B -- yes --> C["total = total + next donation"] C --> B B -- no --> D{"total >= goal?"} D -- yes --> E["Goal met!"] D -- no --> F["Still need goal - total"]

Run it:

Code Runner Challenge

3.09 Example A - Did the Safe Nights campaign reach its goal?

View IPYNB Source
# CODE_RUNNER: 3.09 Example A - Did the Safe Nights campaign reach its goal?

# SEQUENCING: set up the data first
donations = [25, 150, 40, 100, 10, 250]   # dollars, in the order received
goal = 500

# ITERATION: add every donation to a running total
total = 0
for amount in donations:
    total = total + amount

# SELECTION: pick the message
if total >= goal:
    print(f"Goal met! Safe Nights raised ${total}.")
else:
    print(f"Still need ${goal - total} to reach the goal.")
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Same algorithm, written the way the AP exam writes it:

Code Runner Challenge

Same algorithm as the Python above, in College Board pseudocode. Run it, then change the goal to 600 and run it again.

Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Popcorn Hack 1: Translate pseudocode to Python

Volunteers log their hours. Translate this into Python in the runner below, using a for loop (not sum()). It should print 14 and 3.5.

hours ← [3, 5, 2, 4]
total ← 0
FOR EACH h IN hours
{
  total ← total + h
}
average ← total / LENGTH(hours)
DISPLAY(total)
DISPLAY(average)

Code Runner Challenge

3.09 Popcorn 1 - Translate the pseudocode into Python

View IPYNB Source
# CODE_RUNNER: 3.09 Popcorn 1 - Translate the pseudocode into Python

# Step 1: make the hours list

# Step 2: start total at 0

# Step 3: FOR EACH -> for ... in ...: add each h to total

# Step 4: LENGTH(hours) -> len(hours): compute the average

# Step 5: print total, then average
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Part 2: Same Result, or Not?

Example B: different code, same result (AAP-2.L.1). The self-defense workshop holds 12 people. Three ways to ask “is there a seat?”:

def has_seat_a(signed_up):     # check "is there room?"
    if signed_up < 12:
        return True
    else:
        return False

def has_seat_b(signed_up):     # flip it: check "is it full?" and swap the answers
    if signed_up >= 12:
        return False
    else:
        return True

def has_seat_c(signed_up):     # no if at all: the comparison IS True or False
    return signed_up < 12

For 11, 12, and 13, all three return True, False, False, so they’re equivalent. C is the “conditional written as a Boolean expression.” If C used <=, only the 12 test would disagree. That’s why you always test the boundary:

flowchart TD A["Two algorithms"] --> B["Test below the limit"] B --> C["Test AT the limit"] C --> D["Test above the limit"] D --> E{"Same output AND same side effects every time?"} E -- yes --> F["Equivalent"] E -- no --> G["Not equivalent"]

Example C: similar code, different result (AAP-2.L.2). Staff want to count large gifts ($100 or more). The two algorithms differ by four spaces of indentation. Predict both numbers before you run.

Code Runner Challenge

3.09 Example C - Predict both counts BEFORE you run

View IPYNB Source
# CODE_RUNNER: 3.09 Example C - Predict both counts BEFORE you run

donations = [25, 150, 40, 100, 10, 250]

# Algorithm A
count_a = 0
for amount in donations:
    if amount >= 100:
        count_a = count_a + 1       # inside the if: counts only large gifts
print("Algorithm A counted:", count_a)

# Algorithm B: one line moved
count_b = 0
for amount in donations:
    if amount >= 100:
        count_b = count_b + 1
    count_b = count_b + 1           # outside the if: runs for EVERY donation
print("Algorithm B counted:", count_b)
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

A prints 3 (correct). B prints 9: 3 large gifts plus 1 for each of the 6 donations. No error, just a wrong report.

Example D: same result, different side effect. Both of these return 250, the largest gift, but largest_b also sorts the donation log, which scrambles the order the thank-you notes go out in. Same result, different side effect, so they’re not equivalent.

def largest_a(amounts):
    largest = amounts[0]           # only READS the list
    for amount in amounts:
        if amount > largest:
            largest = amount
    return largest

def largest_b(amounts):
    amounts.sort()                 # SIDE EFFECT: reorders the caller's list
    return amounts[-1]

Popcorn Hack 2: Predict, then fix

This should count workshops that are full (12 or more signed up). Self-Defense (12) and Fitness (15) are full, so the answer is 2.

  1. Predict what it prints, and write your guess in the comment.
  2. Run it, then fix the one-character bug.

Code Runner Challenge

3.09 Popcorn 2 - Predict, then fix the full-workshop counter

View IPYNB Source
# CODE_RUNNER: 3.09 Popcorn 2 - Predict, then fix the full-workshop counter

signed_up = [12, 7, 15, 9]   # Self-Defense, Parenting Skills, Fitness, Self-Sufficiency
capacity = 12

full = 0
for count in signed_up:
    if count > capacity:     # hint: what happens at EXACTLY 12?
        full = full + 1

print("Full workshops:", full)

# My prediction before running: ___
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Part 3: Modify and Combine (AAP-2.M)

Most new algorithms aren’t written from scratch. You take a pattern you trust and modify it, or combine two.

Modify: to go from counting matches to collecting them, keep the loop and the if, and change only what you track:

Count Collect
count = 0 matches = []
count = count + 1 matches.append(item)
print(count) print(matches)

Combine: use one algorithm’s answer to decide what happens next, like if any gifts were $100 or more, find the largest one.

Popcorn Hack 3: Modify the counter into a collector

Staff want the names of workshops that still have a seat (fewer than 12). Fill in the TODOs. It should print:

Workshops with open seats: 2
['Parenting Skills', 'Self-Sufficiency']

Code Runner Challenge

3.09 Popcorn 3 - Modify the counter into a collector

View IPYNB Source
# CODE_RUNNER: 3.09 Popcorn 3 - Modify the counter into a collector

workshops = ["Self-Defense", "Parenting Skills", "Fitness", "Self-Sufficiency"]
signed_up = [12, 7, 15, 9]     # signed_up[0] goes with workshops[0], and so on
capacity = 12

open_workshops = []            # COLLECT names instead of counting

for i in range(len(workshops)):          # i = 0, 1, 2, 3
    # TODO 1: replace pass with an if that is True when signed_up[i] < capacity
    pass
        # TODO 2: inside your if, append workshops[i] to open_workshops

# TODO 3: print how many there are, then the list
print("Replace this line")
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

MCQ Check

Answer all 4, then copy your score line.


Homework

The Popcorn Hacks were live checks in class. You are responsible for copying their code, predictions, and output into your own notebook, because the lesson page doesn’t save your work.

Homework Hack: Supply closet restock report

Safe Passage Heals keeps a supply closet with a target amount for each item. Before a donation drive, staff need a restock report. Combine three patterns: collect the items below target, sum the shortages, and find the max shortage. Expected output:

Restock needed:
Blankets: need 12
Shampoo: need 10
Total items needed: 22
Most urgent: Blankets (short by 12)

Socks has exactly 25 of a 25 target, so it is not short (the boundary again). Replace each pass, and keep a comment above every block.

Code Runner Challenge

3.09 Homework - Safe Passage Heals supply restock report

View IPYNB Source
# CODE_RUNNER: 3.09 Homework - Safe Passage Heals supply restock report

items    = ["Toothbrushes", "Blankets", "Socks", "Shampoo", "Notebooks"]
in_stock = [40, 8, 25, 5, 30]      # in the closet now
target   = [30, 20, 25, 15, 30]    # what staff want on hand

# Step 1: COLLECT items below target, and how many of each are needed
short_items = []
short_amounts = []
for i in range(len(items)):
    # TODO 1: if in_stock[i] < target[i], append items[i] and target[i] - in_stock[i]
    pass

# Step 2: SUM the shortages with a loop (no sum())
total_needed = 0
# TODO 2

# Step 3: FIND THE MAX shortage (track its position so you know the item's name)
# TODO 3

# Step 4: COMBINE: print "Fully stocked!" if nothing is short, otherwise the report
# TODO 4
print("Replace this line")
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

References

  • College Board. AP Computer Science Principles Course and Exam Description, Topic 3.9, AAP-2.L and AAP-2.M. https://apcentral.collegeboard.org/media/pdf/ap-computer-science-principles-course-and-exam-description.pdf
  • Safe Passage Heals, San Diego: https://safepassageheals.org/san-diego/ (scenario only; all numbers are made up)
  • Python docs, list.sort(): sorts “in place” (Example D’s side effect)

All Python lessons