3.09 Developing Algorithms
Compare, trace, modify, and combine algorithms in Python and College Board pseudocode.
- Reference Guide
- Lesson Plan
- College Board Requirements
- The Lesson
- Part 1: What Is an Algorithm?
- Code Runner Challenge
- Code Runner Challenge
- Code Runner Challenge
- Part 2: Same Result, or Not?
- Code Runner Challenge
- Code Runner Challenge
- Part 3: Modify and Combine (AAP-2.M)
- Code Runner Challenge
- MCQ Check
- Homework
- Homework Hack: Supply closet restock report
- Code Runner Challenge
- References
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).
Run it:
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.")
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.")
Same algorithm, written the way the AP exam writes it:
Same algorithm as the Python above, in College Board pseudocode. Run it, then change the goal to 600 and run it again.
// Tonight's donations, in the order received
donations ← [25, 150, 40, 100, 10, 250]
goal ← 500
// Add every donation to a running total
total ← 0
FOR EACH amount IN donations
{
total ← total + amount
}
// Pick the message
IF (total ≥ goal)
{
DISPLAY("Goal met! Safe Nights raised $" + total)
}
ELSE
{
remaining ← goal - total
DISPLAY("Still need $" + remaining)
}
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.
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)
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
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
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:
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.
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)
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)
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.
- Predict what it prints, and write your guess in the comment.
- Run it, then fix the one-character bug.
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: ___
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: ___
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']
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")
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")
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.
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")
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")
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)