AP CSP Day 27: List Traversal & Filtering
Share
Two-list algorithms process elements from two lists in parallel, often comparing corresponding elements or building a result list by combining them. A search traversal uses a FOR EACH loop with a Boolean flag variable that flips to true when a target element is found. AP CSP review questions on list traversal frequently ask students to trace algorithms that search for a maximum, minimum, or matching element. Recognizing that a flag initialized to false and never set means the target was not found is a key pattern to internalize.
📚 Study the Concept First (Optional) Click to expand ▼
List Traversal Review: Search Algorithms
Linear Search
Linear search checks each element in a list one at a time until it finds the target or reaches the end. On average, it examines half the list. In the worst case, it examines every element. It works on unsorted lists.
Flag Variable Pattern
A common search pattern uses a Boolean flag initialized to false. As the loop traverses the list, it sets the flag to true the moment the target is found. After the loop, the flag indicates whether the target was present.
Practice Question
What is displayed after the following code runs?
words ← ["cat", "elephant", "dog", "butterfly", "ant"]
longWords ← []
FOR EACH word IN words
{
IF LENGTH(word) > 3
{
APPEND(longWords, word)
}
}
DISPLAY(LENGTH(longWords))Checking each word: "cat" has length 3 (not > 3, skip), "elephant" has length 8 (append), "dog" has length 3 (skip), "butterfly" has length 9 (append), "ant" has length 3 (skip). The longWords list contains ["elephant", "butterfly"], with length 2.
B) Only two words exceed length 3, not three. C) Not all five words pass the filter. D) Two words qualify, not just one.
Students include words with length exactly equal to 3, misreading > as ≥. "cat", "dog", and "ant" each have length 3, which does not satisfy LENGTH(word) > 3.
Count each element carefully and check the comparison operator. Write down the length of each string to avoid mental math errors.
Keep Practicing!
Consistent daily practice is the key to AP CSP success.
AP CSP Resources Get 1-on-1 Help