Algorithms with Selection and Repetition
Help Questions
AP Computer Science A › Algorithms with Selection and Repetition
A mail-sorting machine processes a stack of letters. For each letter, it reads the ZIP code. If the ZIP code is for the local area, the letter is placed in Bin A. Otherwise, it is placed in Bin B. This process continues until the stack is empty. This algorithm combines which two fundamental concepts?
Repetition and sequencing only.
Repetition and selection.
Selection and abstraction.
Sequencing and selection.
Explanation
The process is performed "for each letter" until the stack is empty, which is repetition. Inside that repetition, a decision is made based on the ZIP code ("If the ZIP code is..."), which is selection. Therefore, the algorithm's main structure combines repetition and selection.
Which of the following real-world scenarios is best modeled using only sequencing, without selection or repetition?
Checking every apple in a basket to find all the ones that are bruised.
Repeatedly entering a password until it is accepted by a system.
Choosing between taking a bus or a train based on which one arrives first.
Following the fixed, step-by-step instructions to assemble a piece of furniture.
Explanation
Assembling furniture from a manual typically involves a fixed number of steps that must be performed in a specific order with no decisions or loops. This is a pure sequence. Choice (A) is repetition. Choice (C) is selection. Choice (D) involves repetition (checking every apple) and selection (is it bruised?).
A process for grading an essay is described as: "Read the entire essay from beginning to end. If the essay contains any spelling errors, deduct 5 points from the total score." Which combination of algorithmic concepts is represented?
Sequencing followed by selection.
Selection followed by repetition.
Sequencing followed by repetition.
Repetition followed by sequencing.
Explanation
"Read the entire essay" is the first step in a sequence. "If the essay contains any spelling errors, deduct 5 points" is a single decision based on a condition, which is selection. The process does not describe repeating any action in a loop structure. Therefore, it is a sequence followed by a selection.
An algorithm for a thermostat is described as follows: "Repeatedly check the room temperature. As long as the temperature is below 68 degrees, the heat should remain on." Which algorithmic building block is primarily used in this description?
Repetition, because an action is performed continuously based on a condition.
Data Abstraction, because the specific temperature is represented as a single value.
Selection, because a single decision is made about whether to turn the heat on.
Sequencing, because checking the temperature must happen before running the heat.
Explanation
The process involves "repeatedly" checking and performing an action "as long as" a condition is true. This is the definition of repetition, or a loop. Choice (B) is incorrect because the check is continuous, not a one-time decision. While sequencing (C) is a component of the process, the overarching structure that defines the algorithm is repetition. Data abstraction (D) is a valid concept but does not describe the algorithmic structure.
A traffic light cycles through GREEN, YELLOW, RED for a fixed number of cycles. Inputs are cycles and starting state; output is the printed sequence of states. Example input: cycles 1, start GREEN; output: GREEN, YELLOW, RED. Example input: cycles 2, start RED; output: RED, GREEN, YELLOW, RED, GREEN, YELLOW.
String state = startState;
for (int c = 0; c < cycles; c++) {
for (int t = 0; t < 3; t++) {
System.out.println(state);
if (state.equals("GREEN")) state = "YELLOW";
else if (state.equals("YELLOW")) state = "RED";
else state = "GREEN";
}
}
Consider the algorithm for the traffic light; what is the time complexity in terms of cycles $c$?
$O(c)$ because the inner loop is constant size
$O(3^c)$ because the state changes exponentially
$O(1)$ because there are only three states
$O(c^2)$ because two loops always imply quadratic time
Explanation
This question tests AP Computer Science A skills: understanding algorithms with selection and repetition, specifically analyzing time complexity of nested loops. Time complexity measures how execution time grows with input size, and nested loops often multiply their iteration counts. In this traffic light algorithm, the outer loop runs 'cycles' times, and the inner loop always runs exactly 3 times (once for each light state). Choice B is correct because the inner loop has constant size (3 iterations), making the total iterations 3c, which simplifies to O(c) linear time complexity. Choice C is incorrect because two loops don't always imply quadratic time - it depends on whether both loops scale with input size. To help students: Emphasize that constant-size inner loops don't change the order of growth. Practice calculating iterations by multiplying loop counts and identifying which variables affect runtime.
A traffic light simulation prints states for a total duration in seconds, changing every 5 seconds. Inputs are totalSeconds and startState; output is the printed state at each second. Example input: total 6, start GREEN; output: GREEN printed 5 times, then YELLOW once. Example input: total 5, start RED; output: RED printed 5 times.
String state = startState;
for (int s = 1; s <= totalSeconds; s++) {
System.out.println(state);
if (s % 5 == 0) {
if (state.equals("GREEN")) state = "YELLOW";
else if (state.equals("YELLOW")) state = "RED";
else state = "GREEN";
}
}
Consider the algorithm for the traffic light; what is the output after totalSeconds = 5, startState = GREEN?
GREEN printed 4 times, then YELLOW once
YELLOW printed 5 times because s % 5 triggers immediately
GREEN printed 5 times, then the state changes after printing
GREEN printed once, then YELLOW printed 4 times
Explanation
This question tests AP Computer Science A skills: understanding algorithms with selection and repetition, focusing on modulo operations for periodic events. The modulo operator (%) helps detect when counters reach specific intervals, useful for implementing timed state changes. In this traffic light simulation, the condition 's % 5 == 0' triggers state changes every 5 seconds, but the state change occurs after printing the current state. Choice B is correct because GREEN is printed 5 times (when s = 1, 2, 3, 4, 5), then the state changes to YELLOW after the 5th print when s % 5 == 0 evaluates to true. Choice A is incorrect because it miscounts - GREEN is printed 5 times, not 4. To help students: Emphasize that loop body execution order matters - printing happens before the state change check. Practice tracing loops with modulo conditions to understand periodic behavior.
A school processes grades to compute average, but must ignore any negative entries as invalid. Inputs are gradeList; outputs are average of valid grades and validCount. Example input: 90, -1, 80; output: average 85.0, validCount 2. Example input: -5, -2; output: validCount 0.
int sum = 0;
int validCount = 0;
for (int i = 0; i < gradeList.length; i++) {
if (gradeList<u>i</u> >= 0) {
sum += gradeList<u>i</u>;
validCount++;
}
}
double average = (validCount == 0) ? 0.0 : (double) sum / validCount;
System.out.println(average + "," + validCount);
Consider the algorithm for grade processing; how would you modify the algorithm to also count grades above a threshold efficiently?
Add an if inside the existing loop to increment countAbove
Replace the loop with a single if to check one grade only
Add a second full loop after averaging to count above-threshold
Move sum and validCount inside the loop to reset each iteration
Explanation
This question tests AP Computer Science A skills: understanding algorithms with selection and repetition, focusing on efficient algorithm modification. Efficient algorithms minimize redundant operations by combining related tasks within existing loops rather than creating additional passes through data. To count grades above a threshold while already iterating through the array, the most efficient approach is to add the counting logic within the existing loop. Choice B is correct because adding an if statement inside the existing loop to increment countAbove allows both tasks (summing valid grades and counting above-threshold grades) to be accomplished in a single pass through the data. Choice A is incorrect because adding a second full loop would double the time complexity unnecessarily. To help students: Emphasize the efficiency gained by combining related operations in a single loop. Practice identifying opportunities to merge similar tasks that process the same data.
A chef is following a recipe to bake a cake. One step in the recipe reads, "If the batter is too thick, add one tablespoon of milk." Which fundamental algorithmic concept does this step best illustrate?
Repetition, because the instruction might need to be followed multiple times.
Abstraction, because the details of how to add the milk are not specified.
Sequencing, because it is one step in a specific order of instructions.
Selection, because a decision is made to perform an action based on a specific condition.
Explanation
The step involves making a choice (to add milk or not) based on a condition (the batter's thickness). This is the definition of selection. While the step is part of a larger sequence (A), the core concept illustrated within the step is selection. The instruction is a one-time check, not a loop, so it is not repetition (C). Abstraction (D) is a broader concept; the most precise answer is selection.
Consider an algorithm for finding a specific name in a printed, alphabetized phone book. The process is as follows: 1. Open the book to the middle. 2. If the desired name is on that page, stop. 3. If the name comes alphabetically before the names on the page, repeat the process with the first half of the book. 4. Otherwise, repeat the process with the second half of the book. This entire process is an example of which combination of algorithmic concepts?
Sequencing with no selection or repetition.
Repetition that contains selection.
Selection that contains repetition.
Sequencing followed by a single selection.
Explanation
The overall process is repeated ("repeat the process..."), making it a form of repetition. Within each repetition, a choice is made (go to the first half, second half, or stop) based on comparing the names, which is selection. Therefore, the algorithm is best described as a repetition structure that contains selection logic to guide the next step.
Which part of this algorithm best demonstrates the concept of repetition?
Processing the car by performing a function at each of the three washing stations.
The car entering the wash bay and moving forward on the conveyor belt.
The system checking for the "undercarriage spray" option and activating it if selected.
The entire car wash process from start to finish for a single car.
Explanation
Step 5 describes performing a similar action (pausing and applying a treatment) for a set of items (the three stations). This is a form of repetition, equivalent to a fixed loop that executes three times. Step 2 (and 3) describes selection (B). The other actions are part of the overall sequence (A, D).