Procedures & Lists

📝 Procedures & Lists

Part 1 of 7 — List Operations, Traversals, and Procedure Design

Lists in AP CSP

A list (also called an array) stores an ordered collection of values.

// AP CSP pseudocode uses 1-based indexing!
myList ← ["apple", "banana", "cherry"]
DISPLAY(myList[1])    // "apple" (index 1 is the first element)
DISPLAY(myList[3])    // "cherry"

⚠️ AP CSP lists are 1-indexed (first element at index 1). Most programming languages are 0-indexed.

List Operations

Example

scores ← [90, 85, 78]
APPEND(scores, 92)           // [90, 85, 78, 92]
INSERT(scores, 2, 88)        // [90, 88, 85, 78, 92]
REMOVE(scores, 1)            // [88, 85, 78, 92]
DISPLAY(LENGTH(scores))      // 4

Concept Check 🎯

List Traversal

FOR EACH Loop

total ← 0
FOR EACH score IN scores
{
    total ← total + score
}
average ← total / LENGTH(scores)

Index-Based Loop

i ← 1
REPEAT UNTIL (i > LENGTH(scores))
{
    DISPLAY(scores[i])
    i ← i + 1
}

Common List Algorithms

Find the Maximum

PROCEDURE findMax(list)
{
    max ← list[1]
    FOR EACH item IN list
    {
        IF (item > max)
        {
            max ← item
        }
    }
    RETURN max
}

Filter a List

PROCEDURE getPositives(list)
{
    result ← []
    FOR EACH item IN list
    {
        IF (item > 0)
        {
            APPEND(result, item)
        }
    }
    RETURN result
}

Swap Two Elements

temp ← list[i]
list[i] ← list[j]
list[j] ← temp

Applied Recall ✍️

1. APPEND(list, value) adds the value to the _______ of the list.

2. REMOVE(list, i) removes the element at index i and shifts remaining elements _______.

3. To swap two list elements without losing data, you need a _______ variable.

List Operations 🔍

AP Exam Strategy: Procedures & Lists

• Lists are 1-indexed on the AP exam — first element is list[1], NOT list[0]
• Know all list operations: access, assign, INSERT, APPEND, REMOVE, LENGTH
• INSERT shifts elements RIGHT (list grows). REMOVE shifts elements LEFT (list shrinks)
• The swap algorithm (using temp) appears frequently — memorize it
• Common patterns: sum/average, find max/min, filter, count matches
• FOR EACH is read-only for the loop variable — changes to the variable do NOT change the list

AP-Style Application 🎯

📋 Procedures & Lists

Part 2 of 7 — Key Processes

Procedures Bundle Reusable Logic

A procedure (a.k.a. function or method) is a named, reusable block of instructions. Define once, call many times.

    PROCEDURE greet(name)       DISPLAY("Hello, " + name)

Calling greet("Alex") runs the body with name = "Alex".

Concept Check 🎯

Why Procedures Matter

Lists Hold Many Values

A list is an ordered collection of values, accessed by index.

    grades ← [85, 92, 78, 90]     grades[1] = 85 (in 1-indexed AP pseudocode)     LENGTH(grades) = 4

Common list operations:

Mini-walkthrough

    PROCEDURE average(scores)       total ← 0       FOR EACH s IN scores:         total ← total + s       RETURN total / LENGTH(scores)

Now anywhere we need an average, we call average(myList).

Applied Recall ✍️

1. A named, reusable block of instructions is called a _______.

2. The variable in a procedure's definition that receives a value is called a _______.

3. In AP CSP pseudocode, the first element of a list is at index _______.

Targeted Practice 🔍

AP Exam Strategy: Procedures & Lists

• Know the parameter / argument distinction.
• Be careful with 1-based indexing in AP pseudocode.
• LENGTH, APPEND, INSERT, REMOVE are the core list ops.

AP-Style Application 🎯

📋 Procedures & Lists

Part 3 of 7 — Patterns & Examples

Procedure Patterns

List Patterns

Concept Check 🎯

Map / Filter / Reduce In Pseudocode

    doubled ← [] // map     FOR EACH n IN nums:       APPEND(doubled, n * 2)

    evens ← [] // filter     FOR EACH n IN nums:       IF n MOD 2 = 0 THEN APPEND(evens, n)

    total ← 0 // reduce (sum)     FOR EACH n IN nums:       total ← total + n

These three patterns underlie almost all list processing.

2D Lists (Lists Of Lists)

    grid ← [[1, 2, 3],          [4, 5, 6],          [7, 8, 9]]     grid[2][3] = 6 (row 2, column 3 — 1-indexed)

To process every cell:

    FOR EACH row IN grid:       FOR EACH cell IN row:         PROCESS(cell)

This is a nested loop.

Applied Recall ✍️

1. A pattern that produces a NEW list where each element is f(x) is called _______.

2. A pattern that combines all elements into a single value is called _______.

3. A list of lists, like a grid, is a _______-dimensional list.

Targeted Practice 🔍

AP Exam Strategy: Procedures & List Patterns

• Map / filter / reduce: recognize the pattern → name it.
• 2D lists need nested loops.
• Predicates return true / false; pair them with filter.

AP-Style Application 🎯

📋 Procedures & Lists

Part 4 of 7 — Connections & Interactions

Procedures & Lists Connect Across CSP

Concept Check 🎯

Lists Are Often Procedure Inputs / Outputs

Most non-trivial procedures take or return lists:

    PROCEDURE topThree(scores)       sorted ← SORT(scores, descending)       RETURN [sorted[1], sorted[2], sorted[3]]

Mutability Caution

When a procedure receives a list, modifying it may modify the caller's list (depending on language). To stay safe, document whether your procedure mutates inputs or returns a fresh list.

Pure Functions Are Easier To Test

A pure function (no side effects, output depends only on inputs) can be tested with simple input → expected-output pairs:

This is why pure functions are encouraged in modern code.

Applied Recall ✍️

1. A function whose output depends only on its inputs (and has no side effects) is called _______.

2. A test that verifies a single procedure's behavior is called a _______ test.

3. When a procedure changes the caller's list, we say it _______ the input.

Targeted Practice 🔍

AP Exam Strategy: Cross-Topic Procedures/Lists

• Procedures = the unit of reuse, abstraction, testing, and team-coordination.
• Lists = the most common structured data passed between procedures.
• Pure functions are easier to test, parallelize, and reason about.

AP-Style Application 🎯

📋 Procedures & Lists

Part 5 of 7 — Change Over Time

How Procedures & Lists Have Evolved

Concept Check 🎯

Lists Got A Cousin: Other Collections

AP CSP focuses on lists, but real software uses all of these.

Procedures As Values

Modern languages let you store procedures in variables, pass them as arguments, and return them from other procedures. This makes patterns like map and filter natural.

    doubled ← MAP(nums, lambda x: x * 2)     evens ← FILTER(nums, lambda x: x MOD 2 = 0)

The AP exam emphasizes the conceptual underpinnings even if it uses simpler pseudocode.

Immutability Pressure

Many modern languages favor persistent / immutable lists. Operations return new lists instead of mutating the original. This eliminates whole classes of bugs but requires more memory (mitigated by structural sharing).

Applied Recall ✍️

1. An unordered collection of unique values is called a _______.

2. A collection mapping keys to values is called a _______ or dictionary.

3. An anonymous inline procedure is often called a _______.

Targeted Practice 🔍

AP Exam Strategy: Modern Procedures/Lists

• Functional patterns (map / filter / reduce) are everywhere.
• Procedures can be values (lambdas, callbacks).
• Immutability is increasingly the default in new languages.

AP-Style Application 🎯

📋 Procedures & Lists

Part 6 of 7 — Problem-Solving Workshop

Procedures & Lists Workshop

Concept Check 🎯

Worked: Build A "Top K" Procedure

    PROCEDURE topK(scores, k)       sorted ← SORT(scores, descending)       result ← []       FOR i FROM 1 TO k:         APPEND(result, sorted[i])       RETURN result

Now any caller can ask for the top 3, top 10, etc.

Worked: Compose Map + Filter + Reduce

Sum the squares of even numbers in nums:

    total ← 0     FOR EACH n IN nums:       IF n MOD 2 = 0 THEN         total ← total + n * n

Conceptually: filter (even) → map (square) → reduce (sum).

Worked: 2D Sum

    PROCEDURE gridSum(grid)       total ← 0       FOR EACH row IN grid:         FOR EACH cell IN row:           total ← total + cell       RETURN total

Applied Recall ✍️

1. A "top K" procedure usually first _______ the list, then takes the first k elements.

2. Filter then map then reduce is a common functional _______.

3. Touching every cell in a 2D list requires _______ loops.

Targeted Practice 🔍

AP Exam Strategy: Workshop

• Recognize map / filter / reduce shape from the loop body.
• Top-K = sort + take.
• 2D traversal = nested loops.

AP-Style Application 🎯

📋 Procedures & Lists

Part 7 of 7 — AP Review

AP Exam Recap — Procedures & Lists

Concept Check 🎯

Final Vocab

Common Pitfalls

• Confusing parameter and argument.
• Off-by-one with 1-indexed lists.
• Forgetting to RETURN a value.
• Mutating a caller's list without documenting it.
• Writing one big function instead of decomposing.

Applied Recall ✍️

1. A higher-order procedure takes another _______ as an argument.

2. The number of elements in a list is given by the _______ operation.

3. A function with no side effects whose output depends only on its inputs is called _______.

Targeted Practice 🔍

Final Exam Tips

• Parameter vs. argument: definition vs. call.
• LENGTH, APPEND, INSERT, REMOVE, list[i] are AP's core list ops.
• Map / filter / reduce: name them when you see them.
• Decomposing into named procedures is almost always the right move.

AP-Style Application 🎯