Lesson 12: Developing Algorithms & List Traversals

Warm-Up

Without running it, what question does this code answer?

mystery ← 0
FOR EACH t IN temps
{
    IF (t > 90)
    {
        mystery ← mystery + 1
    }
}
DISPLAY (mystery)

Read the shape: a counter starting at 0, bumped by 1 whenever an element passes a test. It answers: "How many temperatures exceed 90?"

Experienced programmers don't trace this — they recognize it. There are about five list-processing shapes, recombined endlessly on the exam. This lesson teaches you all five, first as recognizable silhouettes, then as code you could write blind.

Core Concept

Algorithms and the three building blocks

An algorithm is a finite set of instructions that accomplishes a task. The CED's foundational claim: every algorithm can be built from three constructs:

• Sequencing — steps in order
• Selection — choosing a path with IF/ELSE
• Iteration — repeating with loops

You've now learned all three. Everything from here — searches, simulations, your Create PT — is these three, composed. Also CED-official: algorithms can be expressed in natural language, flowcharts/diagrams, pseudocode, or code, and the same algorithm can be implemented in different ways; conversely, different algorithms can solve the same problem.

The Big Five list algorithms

1. Sum — accumulator starts at 0, adds every element:

sum ← 0
FOR EACH x IN nums
{
    sum ← sum + x
}

2. Average — sum, then divide by the count after the loop:

sum ← 0
FOR EACH x IN nums
{
    sum ← sum + x
}
avg ← sum / LENGTH(nums)

The division lives outside the loop. Inside-the-loop division is a classic broken variant (it computes garbage — a running "average of averages").

3. Count-matches — counter starts at 0, +1 per element passing a test (the warm-up).

4. Maximum — a champion variable, challenged by every element:

max ← nums[1]
FOR EACH x IN nums
{
    IF (x > max)
    {
        max ← x
    }
}

Initialization is the soul of this one: start max at the first element, not at 0. With max ← 0 and an all-negative list, the code reports 0 — a number not even in the list. Minimum: flip the comparison to x < min. Which brings a general rule: the comparison's direction tells you max (>) vs. min (<); the initialization tells you whether it's honest.

5. Linear search — walk the list; flag when found:

found ← false
FOR EACH x IN roster
{
    IF (x = target)
    {
        found ← true
    }
}

Variants track where (an index counter) or count occurrences. Linear search checks elements one by one, in order — on average more work for longer lists, and it's the only search that works on unsorted data. (Binary search, next lesson, is the fast one — with a prerequisite.)

Reading an unfamiliar algorithm

When the shape isn't instantly familiar, extract three facts:

1. Initialization: what value does the result variable start at? (0 → probably sum/count; first element → max/min; true/false → a search flag)
2. Update rule: what changes it, and under what condition?
3. Post-processing: anything after the loop (a division, a comparison)?

Those three facts identify the algorithm more reliably than reading it line by line — and they're exactly where the exam plants bugs.

Modifying algorithms — the exam's favorite twist

"What happens if line 3 changes to X?" Approach: identify which of the three facts changed.

count ← 0
FOR EACH x IN nums
{
    IF (x ≥ 10)
    {
        count ← count + 1
    }
}

Change ≥ to >: elements exactly 10 stop counting (boundary shift). Change count ← count + 1 to count ← count + x: it becomes a conditional sum — total of the big values, not a tally. Change count ← 0 to count ← 1: everything over-reports by one. Small edits, categorical changes — name the new algorithm, don't re-trace from scratch.

Worked Examples

Example 1 (easy): Name that algorithm

Problem: What does this compute?

r ← scores[1]
FOR EACH s IN scores
{
    IF (s < r)
    {
        r ← s
    }
}
DISPLAY (r)

Strategy: Three facts. Init: first element. Update: replace when smaller. Post: none.

Solution: Minimum of the list. The < points down; honest initialization from the list itself.

Example 2 (medium): The broken maximum

Problem: A student writes a maximum-finder but initializes with max ← 0. For which list does it fail, and what does it output?

(i) [3, 9, 2] (ii) [−4, −1, −7]

Solution: (i): 3 > 0, then 9 > 3 → max = 9 ✓ (works by luck — positives exceed 0). (ii): no element beats 0 → max stays 0, but the true maximum is −1. The code reports a value that isn't in the list.

Interpretation: max ← 0 works exactly until the data goes non-positive — a bug that hides during testing with "nice" data (Lesson 2's boundary lesson, again). The honest fix: max ← nums[1].

Example 3 (medium): Trace a search variant

Problem: What is displayed?

names ← ["Ann", "Raj", "Lu", "Raj"]
spot ← 0
i ← 0
FOR EACH n IN names
{
    i ← i + 1
    IF (n = "Raj")
    {
        spot ← i
    }
}
DISPLAY (spot)

Solution:

Displays 4 — the position of the last match, because later matches overwrite spot.

Interpretation: This search keeps updating on every hit. Finding the first match requires protection (only assign when spot = 0). "First or last occurrence?" is a real exam discrimination — check whether later matches can overwrite.

Example 4 (AP-style): Assemble the algorithm

Problem: A program must display the average of the values in data that are greater than 50. Which is correct?

(A)

sum ← 0
FOR EACH d IN data
{
    IF (d > 50) { sum ← sum + d }
}
DISPLAY (sum / LENGTH(data))

(B)

sum ← 0
count ← 0
FOR EACH d IN data
{
    IF (d > 50)
    {
        sum ← sum + d
        count ← count + 1
    }
}
DISPLAY (sum / count)

(C)

sum ← 0
count ← 0
FOR EACH d IN data
{
    sum ← sum + d
    count ← count + 1
}
DISPLAY (sum / count)

(D)

count ← 0
FOR EACH d IN data
{
    IF (d > 50) { count ← count + 1 }
}
DISPLAY (count / LENGTH(data))

Solution: (B). Averaging a subset needs the subset's sum AND the subset's count — both gated by the same IF. (A) divides the subset's sum by the count of everything (too small a result). (C) averages the whole list, filter forgotten. (D) computes the fraction of elements over 50 — a different question.

Interpretation: Test with tiny data: [60, 40]. Should be 60. (A): 60/2 = 30 ✗. (B): 60/1 = 60 ✓. A two-element test case beats staring.

Common Mistakes

1. Initializing max/min to 0. Fails on all-negative (max) or all-positive (min) data. Initialize from the list: nums[1].
2. Dividing inside the loop. The average's division happens once, after accumulation completes.
3. Subset average with a full-list denominator. Filtered sums need filtered counts — Example 4's exact trap.
4. First vs. last occurrence. An unguarded search assignment keeps overwriting → reports the last match. If the question wants the first, look for the guard.
5. Recognizing the silhouette but skipping the boundary. > 50 vs. ≥ 50 in the filter still matters — silhouette identifies the algorithm, boundary reading gets the actual point.

Practice Problems

z ← 0
FOR EACH v IN vals
{
    z ← z + v
}
DISPLAY (z / LENGTH(vals))

m ← ____
FOR EACH x IN nums
{
    IF (x > m) { m ← x }
}

hits ← 0
FOR EACH g IN [70, 85, 90, 85]
{
    IF (g ≥ 85)
    {
        hits ← hits + 1
    }
}
DISPLAY (hits)

out ← nums[1]
FOR EACH x IN nums
{
    IF (x > out) { out ← x }
}
DISPLAY (out)

w ← ["kiwi", "fig", "plum", "fig"]
first ← 0
i ← 0
FOR EACH x IN w
{
    i ← i + 1
    IF (x = "fig" AND first = 0)
    {
        first ← i
    }
}
DISPLAY (first)

flag ← false
FOR EACH p IN prices
{
    IF (p > 100)
    {
        flag ← true
    }
}

count ← 0
FOR EACH d IN donations
{
    IF (d ≥ 10 AND d ≤ 20)
    {
        count ← count + 1
    }
}
DISPLAY (count)

12 (short response, WR 2(a) style). Write pseudocode that displays how many values in list donations are between 10 and 20 inclusive. Then state what your code displays for donations ← [10, 25, 15, 9, 20].

Create PT Connection

The Big Five are, quite literally, a menu of Create PT algorithms. Every one satisfies the rubric's demands — iteration over your list, selection making a real decision, sequencing throughout — and each has a natural user story:

Pick one, wrap it in the procedure template from Lesson 11's PT section, and your program's core exists. The differentiation between a 4 and a 6 on the PT isn't algorithmic cleverness — it's that you can explain your algorithm precisely in the written responses. You now own that vocabulary: initialization, update rule, post-processing, boundary choice.

count ← 0
FOR EACH d IN donations
{
    IF (d ≥ 10 AND d ≤ 20)
    {
        count ← count + 1
    }
}
DISPLAY (count)