Algorithms Are Built From Three Blocks

An algorithm is a finite set of instructions that accomplishes a task. The AP CSP course makes a strong claim about how every algorithm is built: no matter how complicated a program looks, it is assembled from exactly three building blocks combined and sequenced together. Those blocks are sequencing (running steps in order), selection (an if that chooses a path), and iteration (a loop that repeats). Developing an algorithm is the craft of arranging these three pieces so the program produces the right result.

Up to now you have practiced each block on its own. This topic is where they combine. The single most useful combination in all of AP CSP is a conditional placed inside a loop. That pairing lets a program make a decision repeatedly, once for every item it processes, which is how programs count, filter, and search real data.

The Accumulator Pattern: Count and Sum

The most common algorithm you will build combines a loop, a condition, and a running variable called an accumulator. The recipe never changes: initialize the accumulator before the loop, then update it inside the loop, but only when a condition is met. To count items that meet a rule, start a counter at 0 and add 1 each time the condition is true.

nums = [4, 12, 7, 20]
count = 0
for n in nums:
    if n > 10:
        count = count + 1
print(count)

nums <- [4, 12, 7, 20]
count <- 0
FOR EACH n IN nums
{
    IF (n > 10)
    {
        count <- count + 1
    }
}
DISPLAY(count)

Read it as a repeated decision. For each value n, the program asks "is n > 10?" Only when the answer is yes does it add 1. Here 12 and 20 pass the test, so the final count is 2. The initialization count = 0 must sit before the loop; if it were inside, it would reset on every pass and the count would be wrong.

To sum a subset, use the same shape but add the value itself instead of adding 1. This totals only the items that satisfy the condition.

nums = [3, 6, 9, 12]
total = 0
for n in nums:
    if n % 2 == 0:
        total = total + n
print(total)

nums <- [3, 6, 9, 12]
total <- 0
FOR EACH n IN nums
{
    IF (n MOD 2 = 0)
    {
        total <- total + n
    }
}
DISPLAY(total)

The even values 6 and 12 are added, giving 18. The odd values are skipped entirely. Notice the two algorithms share one skeleton: a zero-initialized accumulator, a loop, and a conditional update. Counting adds 1; summing adds n.

xs = [5, 11, 3, 20]
c = 0
for x in xs:
    if x > 10:
        c = c + 1
print(c)

Finding a Maximum: Best So Far

To find the largest (or smallest) value, use the best so far pattern. Keep a variable holding the best value seen up to this point. For each new value, compare it to the current best, and if the new value is better, update the best. The subtle part is the initialization, and it is a favorite exam trap.

# WRONG: best starts at 0
vals = [-5, -2, -9]
best = 0
for v in vals:
    if v > best:
        best = v
print(best)

# RIGHT: best starts at the first value
best <- vals[1]
FOR EACH v IN vals
{
    IF (v > best)
    {
        best <- v
    }
}
DISPLAY(best)

The buggy version on the left starts best at 0. Every value in the list is negative, so v > best is never true, the best is never updated, and the program wrongly prints 0, a number that is not even in the list. The safe fix, shown on the right, is to start best at the first element of the list. Then the best is always a real value from the data, and the comparison works for negatives, positives, and everything in between.

vals = [-4, -7, -1]
best = 0
for v in vals:
    if v > best:
        best = v
print(best)

Different Algorithms, Same Result

A single problem can be solved by more than one algorithm (AAP-2.L). The two solutions may look nothing alike, may run different numbers of steps, and may use different variables, yet still return the identical output for every input. Recognizing when two algorithms are equivalent, and when they only look equivalent, is a tested skill.

# Algorithm A: count the evens directly
nums = [2, 5, 8]
count = 0
for n in nums:
    if n % 2 == 0:
        count = count + 1
print(count)

# Algorithm B: start at the total, remove the odds
count <- LENGTH(nums)
FOR EACH n IN nums
{
    IF (n MOD 2 = 1)
    {
        count <- count - 1
    }
}
DISPLAY(count)

Both segments compute how many values are even. Algorithm A starts at 0 and counts up when it finds an even. Algorithm B starts at the full length and counts down when it finds an odd. For the list shown, both produce 2. They are different developed algorithms for one problem. Two algorithms are truly equivalent only when they agree on every possible input, not just the one example in front of you, so be careful before declaring two segments the same.

xs = [1, 2, 3, 4]
t = 0
for x in xs:
    if x % 2 == 0:
        t = t + x
print(t)

A Procedure for Building and Tracing

When you develop or trace one of these algorithms, follow one disciplined routine:

1. Name the accumulator and set its starting value before the loop (0 to count or sum; the first element to find a max or min).
2. Enter the loop. For each item, evaluate the condition using the current value.
3. Update the accumulator only when the condition is true. Leave it unchanged otherwise.
4. After the loop finishes, and not before, use or print the accumulator.
5. Sanity check: is the final value one that could actually come from this data?

The order in that routine is the whole game. An update that belongs inside the loop but sits outside it will run only once. An initialization that belongs outside but sits inside will reset every pass. Most algorithm bugs on the exam are one of these two placement mistakes.

Key Vocabulary

Bonus Game: Robot Director

The dreaded robot problems, made playable. Plan a sequence of MOVE_FORWARD, ROTATE_LEFT, and ROTATE_RIGHT commands to steer the AP robot to the flag in as few commands as possible.