AP CSP topic 3.9
Developing Algorithms
Different algorithms can solve the same problem, and some are clearer or faster than others. Programmers often build new algorithms by combining existing ones, such as finding a maximum, computing an average, or counting matches. Two algorithms that look different can still produce the same result for every input. Before writing code, it helps to describe the algorithm in plain steps.
Developing Algorithms vocabulary
- Algorithm: A step-by-step process for solving a problem.
- Existing algorithm: A known, tested algorithm, such as finding the minimum of a list, that can be reused.
- Efficiency: How much time or memory an algorithm uses as its input grows.
- Equivalent: Producing the same output for every possible input.
AP-style practice questions
Try each one, then open the answer. To save your progress, take this quiz in the interactive course.
Algorithm A: Add up all the numbers in the list, then divide by how many there are. Algorithm B: Divide each number by how many there are, then add up the results.
1. Which of the following is true about the two algorithms?
- (A) Only A finds the average
- (B) Only B finds the average
- (C) Both find the average of the list
- (D) Neither finds the average
Show answer
(C) Both find the average of the list Both give the same mathematical result, so they are equivalent algorithms.
2. A programmer needs to find the highest score in a list. Which approach reuses a common existing algorithm?
- (A) Keep a variable for the largest value seen so far and update it while checking each element
- (B) Display every score and look at them
- (C) Sort the list using random numbers
- (D) Remove scores until one remains at random
Show answer
(A) Keep a variable for the largest value seen so far and update it while checking each element Tracking the max while traversing is a standard algorithm.
max ← nums[1]
FOR EACH n IN nums
{
IF (n > max)
{
max ← n
}
}
3. What does the code store in max?
- (A) The first value
- (B) The largest value in nums
- (C) The smallest value in nums
- (D) The number of elements
Show answer
(B) The largest value in nums max is replaced whenever a larger element is found.
4. Which of the following is the best first step before writing code for a new algorithm?
- (A) Pick variable names at random
- (B) Describe the steps in plain language or a flowchart
- (C) Compress the data
- (D) Write the documentation for users
Show answer
(B) Describe the steps in plain language or a flowchart Planning the steps first makes the algorithm easier to code correctly.