Using Programs with | AP CSP Unit 2 Study Guide

Getting Started

Modern applications, from social media feeds to online stores, must manage and process enormous collections of related information—a list of friends, a catalog of products, or a set of scores. To handle this complexity, programs need a way to store and organize data in a structured format. This chapter introduces the list, a fundamental data structure that allows programmers to work with collections of data efficiently.

What You Should Be Able to Do

Explain how a list is used to store and organize a collection of data.
Write an algorithm to traverse a list and access each of its elements.
Design an algorithm that processes a list to find specific information.
Develop an algorithm that filters data from one list to create a new list based on a specific condition.
Trace the execution of a program that uses lists to see how data is processed.

Key Concepts & Application

The Core Idea

Imagine you have a set of numbered mailboxes. Each mailbox can hold one item (a letter), and you can refer to any mailbox by its number. A list in programming works just like this. It is a single container that holds an ordered sequence of items, called elements. Each element has a specific position, or index, which is a number used to access it. In the pseudocode used for AP exams, the first element is always at index 1, the second at index 2, and so on.

Using a list is a form of abstraction. Instead of creating hundreds of individual variables (e.g., score1, score2, score3...), we can create a single list variable (e.g., scores) to hold all of them. This simplifies the program and makes it possible to write a single set of instructions, or an algorithm, that can work with any number of elements.

Logic & Application

Programs perform several common operations on lists. The most fundamental is traversal, which means visiting or processing every element in the list from beginning to end. From this basic pattern, we can build more complex algorithms for searching, filtering, and combining data.

Annotated Pseudocode Examples

1. List Traversal

This algorithm traverses a list of names and displays each one. The FOR EACH loop is a simple and powerful way to process every element without needing to manage an index manually.


// Create a list of student names

studentNames <- ["Amina", "Ben", "Camila", "David"]


// Traversal: Process each name in the list

FOR EACH name IN studentNames

{

  // Display the current name

  DISPLAY(name)

}


// Expected Output:

// "Amina"

// "Ben"

// "Camila"

// "David"

2. Searching a List

This algorithm searches a list of scores to see if a specific score (in this case, 100) exists. It uses a variable as a flag to keep track of whether the value was found.


scores <- [88, 92, 100, 74, 95]

found <- false // A boolean flag, initially set to false


FOR EACH score IN scores

{

  // Check if the current score is the one we're looking for

  IF (score = 100)

  {

    found <- true // Update the flag if we find it

  }

}


// After the loop, display the result

DISPLAY("Was a perfect score found?")

DISPLAY(found)


// Expected Output:

// "Was a perfect score found?"

// true

3. Filtering a List

Filtering involves creating a new list that contains a subset of elements from an original list that meet a certain criteria. This example creates a new list containing only the scores that are 90 or higher.


// The original list of all scores

allScores <- [85, 92, 78, 99, 88, 95]


// 1. Create a new, empty list to store the results

highScores <- []


// 2. Traverse the original list

FOR EACH score IN allScores

{

  // 3. Check if the current score meets the condition

  IF (score >= 90)

  {

    // 4. If it does, add it to the new list

    APPEND(highScores, score)

  }

}


// 5. Display the final filtered list

DISPLAY("High Scores:")

DISPLAY(highScores)


// Expected Output:

// "High Scores:"

// [92, 99, 95]

Tracing & Analysis

Let's trace the "Filtering a List" algorithm to see exactly how the highScores list is built.

Initial State:

allScores = [85, 92, 78, 99, 88, 95]
highScores = []

Iteration	Current `score`	Condition (`score >= 90`)	Action	`highScores` after iteration
1	85	`85 >= 90` is false	None	`[]`
2	92	`92 >= 90` is true	`APPEND(highScores, 92)`	`[92]`
3	78	`78 >= 90` is false	None	`[92]`
4	99	`99 >= 90` is true	`APPEND(highScores, 99)`	`[92, 99]`
5	88	`88 >= 90` is false	None	`[92, 99]`
6	95	`95 >= 90` is true	`APPEND(highScores, 95)`	`[92, 99, 95]`

Final State:highScores contains [92, 99, 95].

Key Terminology & Logic

aList[i]: Accesses the element of aList at index i.
aList[i] <- value: Assigns value to the element of aList at index i.
APPEND(aList, value): Adds value to the end of aList, increasing its length by one.
LENGTH(aList): Evaluates to the number of elements in aList.
FOR EACH item IN aList: A traversal loop that iterates through each item in aList from the first element to the last.

Core Concepts & Terminology

List: A data structure that holds an ordered collection of items, where each item is accessible by a numerical index.
Element: An individual item stored within a list.
Index: A number representing the position of an element in a list. The exam reference sheet uses 1-based indexing, meaning the first element is at index 1.
Traversal: The process of iterating through the elements of a list, one by one, to access or process them.
Filtering: The process of creating a new list containing only the elements from an original list that meet a specified criteria.
Core Logic (List Traversal): A FOR EACH loop is the standard structure for visiting every element in a list.
```
myList <- [10, 20, 30]

FOR EACH item IN myList

{

  DISPLAY(item)

}
```
This code displays each element of myList on a new line.

Core Logic (Filtering Pattern): This pattern involves creating an empty list, traversing a source list, and appending elements that meet a condition.


sourceList <- [1, 2, 3, 4, 5]

resultList <- []

FOR EACH num IN sourceList

{

  IF (num > 3)

  {

    APPEND(resultList, num)

  }

}

// resultList is now [4, 5]

Core Skill Check

Logic Tracing: What is the final value of data after this pseudocode runs: data <- [5, 10, 15]; data[2] <- 20; APPEND(data, 25);?
Debugging: Identify the logic error in this pseudocode intended to find even numbers: nums <- [1, 2, 3, 4]; evens <- []; FOR EACH n IN nums { APPEND(evens, n) }.
Application: Describe a real-world example from a shopping website where an algorithm would need to filter a list of products.

Common Misconceptions & Clarifications

Confusing 1-based and 0-based indexing: Many programming languages start list indices at 0. However, the AP CSP exam and its pseudocode always use 1-based indexing. The first element is at index 1.
Modifying a list while traversing with FOR EACH: The FOR EACH loop is best for accessing or reading data. Modifying the length of a list (e.g., with APPEND or REMOVE) while traversing it can lead to unpredictable behavior or errors.
Forgetting to initialize a new list for filtering: A filter operation does not change the original list. You must always create a new, empty list to store the results of the filter.
Accessing an index that is "out of bounds": Attempting to access myList[5] when the list only has 4 elements will cause an error. An algorithm must ensure its index is always between 1 and LENGTH(myList).

Summary

Lists are a powerful and essential tool for managing collections of related data in a program. By storing data in a list, we can write simple but effective algorithms to traverse, search, and filter information. The pattern of iterating through a list to check each element against a condition is a fundamental building block in computational thinking. Mastering these list operations allows programmers to create sophisticated applications that can process large and complex datasets to solve real-world problems.

Using Programs with Data - AP Computer Science Principles Study Guide