Topic 3.9 Notes – Developing Algorithms

Topic 3.9 is about how algorithms are developed, compared, and modified.

What It Means to Develop an Algorithm

An algorithm is a step-by-step set of instructions that solves a problem. In AP CSP, every algorithm is built from:

• Sequencing (statements in order)
• Selection (IF, IF/ELSE)
• Iteration (REPEAT, REPEAT UNTIL, FOR EACH)

The most important idea here is this:

The way statements are sequenced and combined determines the result.

Change the order of two lines, move a variable update inside a loop, or tweak a condition from > to ≥, and you may get a completely different outcome.

When comparing algorithms, always keep track of:

• Final output
• Final variable values
• Any side effects (like modifying a list)

That’s what the AP questions are really testing.

Different Algorithms for the Same Problem

Same Task, Different Steps

There is almost never just one “correct” algorithm.

Suppose we want to find the maximum value in a list.

One approach:

max ← numbers[1]
FOR EACH num IN numbers
{
   IF (num > max)
   {
      max ← num
   }
}

Another approach:

max ← 0
FOR EACH num IN numbers
{
   IF (num > max)
   {
      max ← num
   }
}

These look similar, but they are not equivalent if the list contains only negative numbers. The first works for all cases. The second fails.

This is exactly the kind of subtle difference the AP exam likes.

Algorithms can differ in:

• Loop type (FOR EACH vs REPEAT UNTIL)
• Starting values
• Order of updates
• Structure of conditionals

They can still solve the same problem correctly if they produce the same result for all possible inputs.

Similar-Looking Algorithms That Are Not Equivalent

Here’s a classic difference:

IF (score ≥ 70)
{
   passed ← true
}
ELSE
{
   passed ← false
}

versus

passed ← (score > 70)

These are not equivalent because one includes 70 and the other does not.

Small changes like:

• > vs ≥
• Updating a counter before checking a condition
• Placing an ELSE in the wrong place

can change the behavior.

When comparing two algorithms on a quiz:

1. Use the same input.
2. Trace step by step.
3. Compare final values and outputs.

If they differ for even one input, they are not equivalent.

Equivalent Boolean Expressions and Conditionals

Some conditionals can be rewritten as Boolean expressions.

Example:

IF (age ≥ 18)
{
   adult ← true
}
ELSE
{
   adult ← false
}

This can be rewritten as:

adult ← (age ≥ 18)

Both produce the same result for every input.

Here’s a helpful comparison:

IF (x MOD 2 = 0)
{
   even ← true
}
ELSE
{
   even ← false
}

even ← (x MOD 2 = 0)

You should also recognize logical equivalences like:

• NOT (A AND B) is the same as (NOT A) OR (NOT B)
• Nested conditionals can sometimes be combined using AND or OR

The key question is always:
Do these produce the same Boolean value for all possible inputs?

Creating and Modifying Algorithms

Algorithms are developed in three main ways:

1. From scratch starting with a problem idea
2. By combining existing algorithms
3. By modifying an existing algorithm

You already know several “building block” algorithms:

• Finding a maximum or minimum
• Computing a sum or average
• Checking if one number is evenly divisible by another (MOD)
• Traversing a list with FOR EACH
• Determining a robot’s path through a maze

You can combine them. For example:

• Use a sum algorithm + divide by LENGTH(list) to compute an average.
• Modify a search algorithm so instead of stopping at the first match, it counts all matches.

This reuse matters because:

• It reduces development time.
• It reduces testing.
• It makes debugging easier.

If a known correct algorithm is reused and your program fails, the bug is probably in how you connected pieces together.

That logic shows up heavily in the Create Performance Task. If you explain how you combined or modified an existing algorithm, that’s strong evidence of understanding.