Algorithm Development (College Board AP® Computer Science Principles): Study Guide
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
trueorfalsecan 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
eligiblefor 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)
Strategy | Example | Benefit |
|---|---|---|
Early exit | Stop searching once the target is found | Avoids processing remaining items |
Stored results | Save a calculated value instead of recalculating | Reduces repeated operations |
Better algorithm | Use binary search instead of linear search | Fewer comparisons on large data sets |
Examiner Tips and Tricks
When the AP exam presents two algorithms and asks whether they are logically equivalent, trace both with the same input and compare outputs.
For the AP Create Performance Task, if your program combines multiple algorithms (e.g., filtering then sorting), explain how each contributes to the overall solution in your written response.
Worked Example
Which of the following is logically equivalent to the code segment below?
IF(x > 10)
{
result ← true
}
ELSE
{
result ← false
}
(A) result ← (x < 10)
(B) result ← (x > 10)
(C) result ← true
(D) result ← (x = 10)
[1]
Answer:
(B) result ← (x > 10) [1 mark]
The IF/ELSE assigns
truewhenx > 10andfalseotherwise — this is exactly whatresult ← (x > 10)evaluates to directly, making them logically equivalent
Unlock more, it's free!
Join the 100,000+ Students that ❤️ Save My Exams
the (exam) results speak for themselves:
Was this revision note helpful?
