Algorithms with Selection and Repetition
Help Questions
AP Computer Science A › Algorithms with Selection and Repetition
A school stores grades in an int[] gradeList; the algorithm iterates to compute average and count grades >= threshold. Inputs are gradeList and threshold; outputs are average and countAbove. Example input: 80, 90, 70, threshold 85; output: average 80.0, countAbove 1. Example input: 100, 60, threshold 70; output: average 80.0, countAbove 1.
// Compute average and count grades at or above threshold
int sum = 0;
int countAbove = 0;
for (int i = 0; i < gradeList.length; i++) {
sum += gradeList<u>i</u>;
if (gradeList<u>i</u> >= threshold) {
countAbove++;
}
}
double average = (double) sum / gradeList.length;
System.out.println(average + "," + countAbove);
Consider the algorithm for processing grades; which part ensures every grade is compared to threshold exactly once?
The cast to double ensures each grade is checked once
The for-loop header iterates once per index in gradeList
The sum variable prevents skipping grades during iteration
The if-statement repeats until countAbove equals threshold
Explanation
This question tests AP Computer Science A skills: understanding algorithms with selection and repetition, focusing on loop control and iteration mechanics. The for-loop structure ensures systematic traversal through arrays by using an index variable that increments from 0 to the array length minus one. In this problem, the for-loop header 'for (int i = 0; i < gradeList.length; i++)' controls the iteration, visiting each array element exactly once. Choice B is correct because the loop header specifically iterates once per index in gradeList, ensuring every grade is accessed through gradeList[i] and compared to the threshold exactly once. Choice A is incorrect because the cast to double only affects the average calculation, not the iteration count. To help students: Emphasize that for-loop headers control iteration count, not the loop body. Practice tracing through loops with index variables to see how each element is accessed exactly once.
A guessing game picks a secret integer; the player repeatedly guesses until correct. Inputs are secret and a sequence of guesses; output is the number of attempts and feedback messages. Example input: secret 7, guesses 3,9,7; output: "Too low", "Too high", attempts 3. Example input: secret 2, guesses 2; output: attempts 1.
int attempts = 0;
int guess = -1;
while (guess != secret) {
guess = getNextGuess();
attempts++;
if (guess < secret) {
System.out.println("Too low");
} else if (guess > secret) {
System.out.println("Too high");
}
}
System.out.println("Attempts: " + attempts);
Consider the algorithm for the guessing game; why is a loop necessary in this part of the algorithm?
It guarantees the first guess is always correct
It prevents attempts from increasing past 1
It makes the feedback messages print only after winning
It allows repeated guesses until the conditional becomes false
Explanation
This question tests AP Computer Science A skills: understanding algorithms with selection and repetition, specifically while loops for indefinite iteration. While loops continue executing their body as long as the condition remains true, making them ideal for situations where the number of iterations is unknown beforehand. In this guessing game, the while loop continues as long as 'guess != secret', allowing the player to make multiple attempts until they guess correctly. Choice B is correct because the while loop allows repeated guesses until the conditional (guess != secret) becomes false, which happens when the correct guess is made. Choice A is incorrect because loops don't guarantee correctness of guesses, they just allow repetition. To help students: Use flowcharts to visualize how while loops check conditions before each iteration. Practice identifying when to use while loops versus for loops based on whether iteration count is known.
A store tracks inventoryCount for one item; transactions update stock until a sentinel ends input. Inputs are starting inventoryCount and a list of (type, amount) transactions; output is final inventoryCount. Example input: start 10, BUY 3, RETURN 2, END; output 9. Example input: start 1, BUY 2, END; output 1.
int inventoryCount = startCount;
while (true) {
String type = getType(); // "BUY", "RETURN", or "END"
if (type.equals("END")) break;
int amount = getAmount();
if (type.equals("BUY")) {
if (amount <= inventoryCount) {
inventoryCount -= amount;
}
} else if (type.equals("RETURN")) {
inventoryCount += amount;
}
}
System.out.println(inventoryCount);
Consider the algorithm for inventory updates; which part ensures stock never becomes negative after a BUY?
The break statement resets inventoryCount to zero safely
The conditional amount <= inventoryCount guards the decrement
The RETURN branch compensates for any negative inventory later
The while(true) loop prevents any subtraction from occurring
Explanation
This question tests AP Computer Science A skills: understanding algorithms with selection and repetition, focusing on conditional logic within loops. Selection statements allow algorithms to make decisions based on conditions, preventing invalid operations like creating negative inventory. In this inventory system, the nested if-statement 'if (amount <= inventoryCount)' acts as a guard condition before the decrement operation. Choice C is correct because the conditional 'amount <= inventoryCount' guards the decrement, only allowing purchases when sufficient inventory exists, thus preventing negative stock. Choice A is incorrect because while(true) creates an infinite loop that's broken by the END command, not preventing subtraction. To help students: Teach the concept of guard conditions that protect against invalid states. Practice writing conditions that validate operations before executing them, especially in business logic scenarios.
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(1)$ because there are only three states
$O(c)$ because the inner loop is constant size
$O(3^c)$ because the state changes exponentially
$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 weather station stores daily temperatures in an int[] temps; the algorithm finds hottest and coldest days. Inputs are temps; outputs are minTemp and maxTemp. Example input: 72, 68, 75; output: min 68, max 75. Example input: 50; output: min 50, max 50.
int minTemp = temps<u>0</u>;
int maxTemp = temps<u>0</u>;
for (int i = 1; i < temps.length; i++) {
if (temps<u>i</u> < minTemp) minTemp = temps<u>i</u>;
if (temps<u>i</u> > maxTemp) maxTemp = temps<u>i</u>;
}
System.out.println(minTemp + "," + maxTemp);
Consider the algorithm for weather analysis; which part ensures correctness when temps has exactly one element?
Using two if-statements forces at least two iterations
Printing min and max guarantees they were updated in the loop
Starting i at 1 avoids accessing temps[0] entirely
Initializing minTemp and maxTemp to temps[0] handles length 1
Explanation
This question tests AP Computer Science A skills: understanding algorithms with selection and repetition, focusing on edge case handling and initialization. Proper initialization ensures algorithms work correctly even with minimal input, such as single-element arrays. In this weather analysis algorithm, both minTemp and maxTemp are initialized to temps[0], which handles the edge case where the array has only one element. Choice B is correct because initializing minTemp and maxTemp to temps[0] ensures that when temps has length 1, both variables already contain the only value, and the loop body never executes (since i starts at 1). Choice A is incorrect because starting i at 1 is intentional to avoid redundant comparison of temps[0] with itself. To help students: Teach the importance of initialization values that handle edge cases. Practice tracing algorithms with minimal inputs like single-element or empty arrays.
A guessing game stops after maxAttempts to prevent endless play. Inputs are secret, maxAttempts, and guesses; output is either success with attempts or "Out of tries". Example input: secret 5, max 2, guesses 1,3; output: Out of tries. Example input: secret 5, max 3, guesses 1,5; output: attempts 2.
int attempts = 0;
boolean won = false;
while (attempts < maxAttempts && !won) {
int guess = getNextGuess();
attempts++;
if (guess == secret) won = true;
else if (guess < secret) System.out.println("Too low");
else System.out.println("Too high");
}
if (won) System.out.println("Attempts: " + attempts);
else System.out.println("Out of tries");
Consider the algorithm for the guessing game; which part ensures the loop cannot run indefinitely?
The guess variable resets attempts to zero after each input
The feedback messages slow the loop until it stops naturally
The else-if chain forces the secret to change each iteration
The attempts < maxAttempts condition bounds the iterations
Explanation
This question tests AP Computer Science A skills: understanding algorithms with selection and repetition, specifically loop termination conditions. Compound conditions in while loops ensure multiple criteria can stop iteration, preventing infinite loops in interactive programs. In this limited guessing game, the while loop condition 'attempts < maxAttempts && !won' uses two criteria to control loop termination. Choice A is correct because the 'attempts < maxAttempts' condition bounds the iterations, ensuring the loop stops after maxAttempts regardless of whether the player wins, thus preventing infinite execution. Choice B is incorrect because feedback messages don't control loop termination, they only provide information to the player. To help students: Teach how compound conditions with && create multiple exit criteria. Practice writing loops that must terminate based on either success conditions or failure limits.
A store inventory algorithm logs each transaction and updates stock until END. Inputs are startCount and n transactions; output is final inventoryCount and processed transaction count. Example input: start 5, RETURN 1, BUY 3, END; output: inventory 3, processed 2. Example input: start 0, BUY 1, END; output: inventory 0, processed 1.
int inventoryCount = startCount;
int processed = 0;
while (true) {
String type = getType();
if (type.equals("END")) break;
int amount = getAmount();
processed++;
if (type.equals("BUY") && amount <= inventoryCount) inventoryCount -= amount;
else if (type.equals("RETURN")) inventoryCount += amount;
}
System.out.println(inventoryCount + "," + processed);
Consider the algorithm for inventory management; what is the time complexity if there are $n$ transactions before END?
$O(n)$ because each transaction is processed once
$O(1)$ because inventoryCount is a single integer
$O(n^2)$ because conditionals multiply loop iterations
$O(\log n)$ because END causes a binary search-like stop
Explanation
This question tests AP Computer Science A skills: understanding algorithms with selection and repetition, focusing on time complexity analysis of sentinel-controlled loops. Sentinel values like 'END' terminate loops after processing a variable number of inputs, and complexity depends on the number of items processed. In this inventory algorithm, each transaction (BUY or RETURN) is processed exactly once before the END sentinel is encountered. Choice B is correct because the algorithm processes each of the n transactions once, performing constant-time operations (comparison and arithmetic) for each, resulting in O(n) linear time complexity. Choice C is incorrect because conditionals within the loop don't create nested iteration - they only affect which constant-time operation occurs. To help students: Clarify that time complexity counts iterations, not the number of conditional branches. Practice analyzing loops that process sequences terminated by sentinel values.
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 once, then YELLOW printed 4 times
GREEN printed 5 times, then the state changes after printing
GREEN printed 4 times, then YELLOW once
YELLOW printed 5 times because s % 5 triggers immediately
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?
Move sum and validCount inside the loop to reset each iteration
Replace the loop with a single if to check one grade only
Add a second full loop after averaging to count above-threshold
Add an if inside the existing loop to increment countAbove
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.