Algorithm Development (College Board AP® Computer Science Principles): Revision Note

Algorithm alternatives

Why can problems have multiple algorithmic solutions?

• Most problems can be solved using more than one algorithm, each taking a different approach to reach the same goal

• Different correct algorithms for the same problem can have different efficiencies

• Algorithms that appear similar can yield different side effects or results

• Choosing between algorithms involves evaluating trade-offs such as readability, efficiency, and correctness

Comparing alternative algorithms

• Two algorithms can solve the same problem but differ in the number of steps, the order of operations, or the conditions they check

• Example: finding the minimum value in a list

Algorithm A: track the smallest value:

min ← list[1]
FOR EACH item IN list
{
   IF(item < min)
   {
      min ← item
   }
}
DISPLAY(min)
 

Algorithm B: sort first, then take the first element:

Sort list in ascending order
DISPLAY(list[1])
 

• Both produce the correct minimum, but Algorithm A checks every element once, while Algorithm B requires sorting the entire list first

Logical equivalence

What is logical equivalence?

• Two algorithms are logically equivalent if they produce the same output for every possible input

• A selection structure (IF/ELSE) can be rewritten using Boolean expressions, and vice versa

Selection-Boolean equivalence

• An IF/ELSE block that sets a variable to true or false can be replaced with a single Boolean assignment

Using selection:

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

Using a Boolean expression:

eligible ← (age ≥ 18)
 

• Both are logically equivalent; they produce the same value of eligible for any input

Combining & reusing algorithms

How are algorithms combined?

• Algorithms can be created from an idea, by combining existing algorithms, or by modifying existing algorithms

• Existing algorithms can also be modified to fit a new problem rather than rewritten from scratch, for example, a linear search that returns the first match can be modified to return a count of all matches

• Each smaller algorithm handles one part of the problem, and its outputs feed into the next step

• Example: a program that finds the average of positive numbers in a list combines:

  • A loop to iterate through the list

  • A conditional to filter positive numbers

  • Arithmetic to calculate the sum and count

  • A division to compute the average

Reusing common algorithms

• Common algorithms are well-known solutions that appear across many programs, such as:

  • Determining the maximum or minimum value of two or more numbers

  • Computing the sum or average of two or more numbers

  • Identifying if an integer is or is not evenly divisible by another integer

  • Determining a robot's path through a maze

• Using existing correct algorithms as building blocks has three benefits: reducing development time, reducing testing, and simplifying the identification of errors

Efficiency benefits

What makes one algorithm more efficient than another?

• Efficiency describes how many steps or how much time an algorithm requires to complete

• An algorithm that solves a problem in fewer steps is more efficient

• Efficiency matters most when working with large data sets, where small differences in approach can lead to significant differences in execution time

Algorithm optimization

• Optimization involves modifying an algorithm to reduce unnecessary steps

• Common strategies include:

  • Exiting a loop early once the answer is found

  • Avoiding redundant calculations by storing results

  • Choosing a more efficient algorithm for the task (e.g., binary search over linear search for sorted data)