Big Idea 3: Algorithms and Programming

Programs, Algorithms, and AP CSP Pseudocode

A program is a precise set of instructions that a computer can carry out. An algorithm is a step-by-step process for solving a problem or accomplishing a task. The key difference is that an algorithm is the idea (the recipe), while a program is the implementation of that idea in a language the computer can execute.

Algorithms show up in everyday life: recipes, directions to get somewhere, instructions for taking medicine, or a checklist for completing a task. In computer science, algorithms are the steps used to solve problems and automate processes, and they are implemented with software. Examples include programs that calculate grade averages, run an air conditioner when the room temperature reaches 78°F, or compute the shortest GPS route from home to school.

Programs are often built from modules (sections of code) that may work independently or be combined with other modules. These modules typically read input values, perform computations, and produce output. A major advantage of algorithms is that once created, they can be reused, combined for more complex problem solving, or modified for new purposes.

In AP Computer Science Principles, you’re often asked to reason about programs written in a standardized AP pseudocode. The exam is not testing whether you memorized one specific language’s punctuation. It’s testing whether you can read, trace, and design algorithms.

What “running a program” really means

When a program runs, it follows instructions in order unless an instruction changes the flow (like an IF statement, a procedure call, or a loop). Thinking of execution as a moving “instruction pointer” helps you avoid common tracing mistakes:

• Sequencing: statements execute in the order they appear.
• Selection: the program chooses between paths based on a condition.
• Iteration: the program repeats a block of statements.

These three control structures form the backbone of essentially all programs you’ll see in this unit.

The AP pseudocode basics you must internalize

AP pseudocode uses a consistent style:

• Assignment uses a left arrow: x ← expression (store a value into a variable).
• Equality test uses = inside conditions: IF x = 5.
• Lists are 1-indexed: the first element is at index 1, not 0.
• Blocks are shown with indentation and keywords like IF ... / ELSE / REPEAT.

A subtle but important point: assignment (←) is not “a math equation.” It’s an instruction that changes stored state. After x ← x + 1, the value of x has increased.

Reading code vs. writing code

On the exam, a lot of “programming” is careful reading:

• Tracing: step through line by line, tracking variable values.
• Predicting output: decide what is displayed/returned.
• Identifying equivalence: decide whether two snippets do the same thing.
• Debugging: locate the logic error, often involving conditionals, loop bounds, or list indexing.

When you write algorithms, you practice the same skill from the other direction: you decide what steps a computer must follow to guarantee the correct result.

Exam Focus

• Typical question patterns:
  • Trace a short pseudocode program and determine the final value of a variable or what gets displayed.
  • Choose which code segment correctly implements a described algorithm.
  • Identify which change fixes a bug (often in a condition, loop, or index).
• Common mistakes:
  • Treating x ← x + 1 like an impossible math statement instead of an update.
  • Forgetting that lists are 1-indexed in AP pseudocode.
  • Skipping steps when tracing (especially inside loops or nested conditionals).

Variables, Data Types, Assignment, and Expressions

A variable is a named storage location (a placeholder) for a value a program needs to use. Variables matter because they let programs remember information: user input, intermediate results, counts, totals, and “best-so-far” values.

Variables are also a form of abstraction: you typically don’t need to know the details of how or where a value is stored in memory to use it correctly. Since variables are used constantly, naming them well improves readability and reduces mistakes.

Data types you’ll reason about

AP CSP questions commonly involve these kinds of values:

• Numbers (integers and sometimes non-integers)
• Booleans (true / false)
• Strings (text)
• Lists (ordered collections)

Even when the exam doesn’t say “type,” type still matters because operations only make sense for compatible values. Adding numbers is different from concatenating strings.

Strings as data

A string is a text field: a series of characters denoted with quotation marks. Any character, number, or symbol can be part of a string. When numbers appear inside a string (for example, in a street address like "742"), they are treated as text, not as a number you can calculate with.

Common string operations include:

• Concatenation (joining strings)
• Substring extraction using a built-in operation on the AP reference sheet

Assignment and state (and overwriting)

Assignment (←) changes program state by storing a value in a variable. The variable name is always on the left of the arrow. The computer evaluates the entire right-hand side first, then stores the result into the left-hand variable.

Assignment overwrites the previous value. If score ← 10 and later score ← 11, the value 10 is gone; the variable now stores 11.

A common misconception is to read assignment as a symmetric relationship. It is not. This matters most when the same variable appears on both sides:

• x ← x + 3 means “take the old x, add 3, store the result back into x.”

It’s also important to recognize invalid assignment direction. Writing something like 10 ← score (putting a non-variable on the left) or reversing the arrow direction is not a valid assignment statement.

Expressions and order of operations

An expression is a calculation that evaluates to a single value. That value might be stored (assigned to a variable), displayed on a screen, or printed.

You’ll see arithmetic operators like +, -, *, /, and also MOD:

• a MOD b gives the remainder when a is divided by b.

MOD is especially useful for checking patterns:

• Even/odd: n MOD 2 = 0 means even
• Every kth item: index MOD k = 0

When evaluating expressions, apply standard order of operations. A common mnemonic is PEMDAS:

• P: Parentheses
• E: Exponents
• M: Multiplication
• D: Division
• A: Addition
• S: Subtraction

Worked example: updating variables

Suppose you want to compute a running total after adding new values.

total ← 0
total ← total + 5
total ← total + 2
DISPLAY(total)

Step-by-step reasoning:

• Start: total is 0
• After adding 5: total becomes 5
• After adding 2: total becomes 7
• Display shows 7

The key skill is tracking the variable’s changing value across time.

Exam Focus

• Typical question patterns:
  • Determine the final values of variables after several assignments.
  • Use MOD to reason about parity (even/odd) or repeating patterns.
  • Predict what a string operation (like substring or concatenation) produces.
• Common mistakes:
  • Confusing assignment (←) with comparison (=).
  • Losing track of the “current” value of a variable during tracing.
  • Misinterpreting MOD (it’s remainder, not division).

Boolean Logic and Conditionals

A Boolean value is either true or false. Boolean logic matters because it is how programs make decisions. Booleans are memory-efficient (a Boolean can be represented with a single bit), and they are foundational to readable, correct code.

Comparisons produce booleans

A comparison operator checks a relationship and evaluates to true or false, such as:

• x = y, x ≠ y
• x < y, x > y, x ≤ y, x ≥ y

The important idea is that conditions are expressions too; they just evaluate to a Boolean.

Logical operators: AND, OR, NOT

You build more complex conditions using:

• AND: true only if both sides are true
• OR: true if at least one side is true
• NOT: flips true/false

This matters in real scenarios. For example, “allow login if the password is correct AND the account is not locked.”

Selection with IF / ELSE

A conditional statement chooses what to execute based on a condition:

• Evaluate the condition.
• If it’s true, execute the “then” block.
• Otherwise, execute the “else” block (if present).

Example:

IF score ≥ 90
  grade ← "A"
ELSE
  grade ← "Not A"

In some text-based programming languages, the code to execute is grouped with curly braces { } and indentation is used to make structure visible. Indentation and matching block markers are both used to prevent missing an ending brace/ending block.

A common misconception is thinking both branches might run. They won’t; only one path is taken each time the IF is evaluated.

Nested conditionals

A nested conditional is an IF inside another IF/ELSE branch. Nesting is useful when you have multi-step decision rules.

For example, letter grades:

IF score ≥ 90
  grade ← "A"
ELSE
  IF score ≥ 80
    grade ← "B"
  ELSE
    grade ← "C or below"

This works because you test the most restrictive condition first.

De Morgan’s Law (common logic pitfall)

When you negate a compound condition, you must negate each part and swap AND/OR:

• NOT (A AND B) is equivalent to (NOT A) OR (NOT B)
• NOT (A OR B) is equivalent to (NOT A) AND (NOT B)

Worked example: tracing a conditional with AND

age ← 16
hasID ← true

IF age ≥ 18 AND hasID = true
  DISPLAY("Entry allowed")
ELSE
  DISPLAY("Entry denied")

• age ≥ 18 is false
• hasID = true is true
• false AND true is false
• So it displays “Entry denied”

Exam Focus

• Typical question patterns:
  • Evaluate a compound Boolean expression and determine which branch executes.
  • Rewrite or choose an equivalent logical condition.
  • Trace nested conditionals to determine outputs.
• Common mistakes:
  • Mixing up AND vs OR (AND is stricter; OR is more permissive).
  • Negating a condition incorrectly (especially NOT (A AND B)).
  • Forgetting that comparisons like x = y produce a Boolean value.

Iteration: REPEAT, REPEAT UNTIL, and Loop Reasoning

Iteration (also called repetitive or iterative statements) means repeating a set of instructions. Loops matter because they let you process data at scale: handle every item in a list, repeat until the user enters valid input, simulate many trials, and more.

A useful mental model is: a loop tells the computer, “keep doing this pattern until a stopping rule says you’re done.”

REPEAT n TIMES (count-controlled loops)

A count-controlled loop repeats a fixed number of times.

Example:

sum ← 0
REPEAT 5 TIMES
  sum ← sum + 10
DISPLAY(sum)

This adds 10 five times, resulting in 50.

REPEAT UNTIL (condition-controlled loops)

A condition-controlled loop keeps repeating until a condition becomes true.

Key meaning: REPEAT UNTIL condition repeats while the condition is false, and stops when it becomes true.

Example (input validation conceptually):

REPEAT UNTIL password = "secret"
  password ← INPUT()
DISPLAY("Access granted")

This continues asking until the password is correct. The loop ends when password = "secret" evaluates to true.

Infinite loops and termination

A loop must have a realistic way to end (termination). When you design or debug loops, ask:

1. What must become true for the loop to stop?
2. Does something inside the loop change the state in a way that makes that stop condition more likely?

If nothing changes, the loop can become infinite.

Off-by-one errors

An off-by-one error happens when a loop runs one too many or one too few times. This is especially common with boundaries and list indices (and AP pseudocode lists are 1-indexed).

Worked example: using REPEAT UNTIL carefully

Suppose you want to flip a coin repeatedly until you get heads. Represent heads as 1 and tails as 0.

result ← 0
count ← 0
REPEAT UNTIL result = 1
  result ← RANDOM(0, 1)
  count ← count + 1
DISPLAY(count)

The loop keeps repeating until result becomes 1. Termination is only probabilistically guaranteed here, but you can still trace the logic correctly.

Exam Focus

• Typical question patterns:
  • Determine how many times a loop runs and what value a variable has afterward.
  • Identify whether a loop terminates and under what conditions.
  • Choose the loop structure that matches a described task (fixed repetitions vs repeat until).
• Common mistakes:
  • Reversing the meaning of REPEAT UNTIL (it stops when the condition becomes true).
  • Forgetting to update a variable that affects the loop condition (causing infinite loops).
  • Off-by-one errors when loop iterations correspond to list indices.

Lists and Data Abstraction

A list is an ordered collection of elements (items). Lists matter because many real-world problems involve handling multiple related values: test scores, sensor readings, messages, pixels, purchases, locations, and more.

Data abstraction is the practice of representing complex data with a simpler structure. A popular way to describe abstraction is information hiding: you bundle related pieces so you can work with them as a unit, without constantly thinking about low-level details. Just as related program statements are bundled together into modules, related program variables can be bundled together into a list. This lets you think about data hierarchically.

A list is a classic example of data abstraction because you can give one name to a set of memory cells. For example, using colorList ← ["red", "blue", "green"] is more manageable than having three separate variables like color1, color2, color3.

1-indexing in AP pseudocode

AP CSP pseudocode uses 1-based indexing:

• list[1] is the first element
• list[LENGTH(list)] is the last element

For example, if aList ← [3, 7, 11], then aList[1] is 3, aList[2] is 7, and aList[3] is 11.

Lists, elements, indices, and “arrays”

• Individual items in a list are called elements.
• Elements are accessed by position using an index.
• Index positions are always integers and are written in square brackets: aList[index].

Lists are also called arrays in some programming languages.

A list in a program can be a collection of numbers, words, phrases, or a combination of these. Often a single list contains one type of data, although some programming languages allow different types in the same list.

Built-in list operations (conceptual toolkit)

The AP reference sheet includes standard list operations (names may vary slightly by version, but the ideas are consistent):

• Getting an element by index: aList[i]
• Setting an element: aList[i] ← value
• Length: LENGTH(aList)
• INSERT at a position: inserting at index i causes elements to the right to shift right one position to make room.
• APPEND to the end: adds a new element to the end, increasing list size by one.
• REMOVE at a position: deletes the element at index i and shifts remaining elements left; the list size decreases by one.

Why data abstraction improves programs

Data abstraction helps in two main ways:

1. Manage complexity: You can talk about “the list of scores” instead of score1, score2, …, score100.
2. Enable generic algorithms: You can write one procedure to compute an average no matter how many items there are.

A useful analogy is a spreadsheet column: you treat the whole column as a collection and perform operations across it.

Worked example: storing and updating values

scores ← [90, 84, 100]

scores[2] ← scores[2] + 5
DISPLAY(scores)

Reasoning:

• The second score is 84.
• After update, it becomes 89.
• The list becomes [90, 89, 100].

Common list pitfalls

• Index out of range: trying to access scores[0] or scores[4] in the example above.
• Confusing position and value: the index is where the item sits; the value is what’s stored.
• Modifying a list while iterating: removing items while traversing can skip elements because indices shift.

Exam Focus

• Typical question patterns:
  • Trace code that reads or updates list elements and determine the final list.
  • Use LENGTH to reason about valid indices or loop bounds.
  • Explain why using a list (data abstraction) is beneficial compared with many variables.
• Common mistakes:
  • Forgetting that AP lists start at index 1.
  • Assuming indices don’t change after insertion/removal.
  • Mixing up the element (value) with its index (position).

Traversing Lists and Common List Algorithms

Traversing a list means visiting its elements in a systematic way, typically from first to last. Traversal is how you turn a list from stored data into useful information such as totals, averages, maximums, filtered results, or search outcomes.

FOR EACH traversal (element-based)

A common traversal pattern is:

FOR EACH item IN aList
  (do something with item)

This automatically repeats the code once for each element in the list. The programmer chooses the name of the iteration variable (like item). Each pass assigns the next element’s value into that variable.

Example: compute a sum.

total ← 0
FOR EACH n IN nums
  total ← total + n
DISPLAY(total)

Index-based traversal (position matters)

Sometimes you need indices (to update the list, compare neighbors, coordinate parallel lists, or detect “every 3rd item”). In AP pseudocode, you commonly loop i from 1 to LENGTH(aList) and access aList[i].

Common algorithms: max/min, sum, average

Some algorithms appear constantly:

• Determining the maximum or minimum value from two or more numbers
• Calculating the sum and average of a group of numbers

For maximum of two numbers conceptually:

• Compare the two numbers.
• Store the larger as the maximum.

For minimum of two numbers:

• Compare the two numbers.
• Store the smaller as the minimum.

If you have more than two numbers, a computer still compares only two at a time: it keeps a “current largest” (or “current smallest”) and compares each next number to it.

For average, one key element is keeping a count of how many numbers you’ve added so you can compute the average correctly.

Worked example: find the maximum in a list using REPEAT UNTIL

Here is a typical max-finding algorithm that traverses a list of grades using an index and a REPEAT UNTIL loop:

grades ← [88, 91, 72, 99, 85]

i ← 1
maxSoFar ← grades[1]

REPEAT UNTIL i > LENGTH(grades)
  IF grades[i] > maxSoFar
    maxSoFar ← grades[i]
  i ← i + 1

DISPLAY(maxSoFar)

Worked example: sum and average of values in a list

A typical sum/average algorithm looks like this:

nums ← [3, 7, 11]

sum ← 0
count ← 0

FOR EACH n IN nums
  sum ← sum + n
  count ← count + 1

DISPLAY(sum)
DISPLAY(sum / count)

Filtering: building a new list from a list

A very common algorithm is filtering: keep only items that meet a condition.

Example: keep only passing scores.

passing ← []
FOR EACH s IN scores
  IF s ≥ 70
    APPEND(passing, s)
DISPLAY(passing)

This pattern avoids the complexity of removing elements from the original list while iterating.

Searching a list (concept)

Searching answers: “Is a value present?” or “Where is it?” The most basic approach is linear search (also called sequential search): check each record from beginning to end until you find the target or reach the end.

Aggregation: count, min/max, average

Aggregation means combining many values into one summary value.

Example: count evens.

count ← 0
FOR EACH n IN nums
  IF n MOD 2 = 0
    count ← count + 1
DISPLAY(count)

A major source of bugs is forgetting to initialize accumulators like count ← 0 or sum ← 0 before the loop.

Exam Focus

• Typical question patterns:
  • Determine the result of a traversal (sum, count, filtered list, max/min, or found/not found).
  • Identify which algorithm correctly processes all elements exactly once.
  • Compare two traversals and decide if they are equivalent.
• Common mistakes:
  • Forgetting to initialize an accumulator before the loop.
  • Off-by-one errors in index-based traversals (especially end conditions).
  • Removing from a list while traversing, causing skipped items.

Developing Algorithms and Reasoning About Correctness

An algorithm becomes powerful when you combine sequencing, conditionals, and loops into a coherent plan. In AP CSP, you’re often given a problem statement and asked which code best matches it, whether two implementations are equivalent, or whether an algorithm always works.

A practical process for algorithm development

When you design an algorithm, it helps to think in stages:

1. Clarify the goal: What exactly should the output be?
2. Identify inputs: What information do you start with?
3. Choose a representation: Are you using a list, a number, a string, multiple variables?
4. Pick a strategy: traversal, filtering, counting, searching, repeated refinement, etc.
5. Test with examples: try small cases, edge cases, and typical cases.

Worked example: average of values above a threshold (avoid divide-by-zero)

Goal: Given a list scores, compute the average of the scores that are at least 70. If none are at least 70, avoid dividing by 0.

sum ← 0
count ← 0

FOR EACH s IN scores
  IF s ≥ 70
    sum ← sum + s
    count ← count + 1

IF count = 0
  DISPLAY("No passing scores")
ELSE
  DISPLAY(sum / count)

If you skip the special case, you could attempt sum / 0, which is undefined.

Worked example: find the first position of a target (flag pattern)

Goal: Find the index of the first occurrence of target in aList, or display “not found”.

pos ← 0
i ← 1

REPEAT UNTIL i > LENGTH(aList) OR pos ≠ 0
  IF aList[i] = target
    pos ← i
  i ← i + 1

IF pos = 0
  DISPLAY("not found")
ELSE
  DISPLAY(pos)

This uses pos as a flag meaning “have we found it yet?”

Testing and debugging

Programs rarely work perfectly on the first attempt. Testing and debugging are part of programming.

Good testing uses purposeful inputs:

• Typical cases (normal inputs)
• Edge cases (smallest/largest, empty list, single element)
• Special cases (no matches, all matches, repeated values)

Most AP CSP debugging is logic debugging:

• Trace with a table (record variable values after each step).
• Check loop boundaries.
• Check condition logic (AND vs OR, correct use of NOT).
• Use smaller examples.

Correctness (does it always work?)

Reasoning about correctness means asking: for every valid input, does this algorithm produce the intended output? A practical way to reason is to track an invariant-like claim.

Example claim for a “find max” traversal:

• After processing the first k items, maxSoFar is the maximum of those k items.

If that stays true each iteration, then when the loop ends, maxSoFar is the maximum of the whole list.

Worked example: finding a maximum (and a common bug)

Correct approach:

maxSoFar ← nums[1]
FOR EACH n IN nums
  IF n > maxSoFar
    maxSoFar ← n
DISPLAY(maxSoFar)

A common bug is initializing maxSoFar ← 0. That fails if all numbers are negative. Initializing to the first list element avoids that issue.

Exam Focus

• Typical question patterns:
  • Choose which code segment correctly implements a multi-step algorithm description.
  • Identify edge cases where an algorithm fails (empty list, no matches, single-element list).
  • Identify which test case would expose a bug.
  • Determine where a logic error occurs (wrong condition, wrong initialization, wrong update order).
  • Reason about correctness for all inputs, especially edge cases.
• Common mistakes:
  • Not handling edge cases like “no items match,” leading to divide-by-zero or wrong outputs.
  • Incorrect loop stopping conditions (stopping too early or too late).
  • Updating variables in the wrong order inside the loop.
  • Only testing “happy path” inputs and ignoring edge cases (empty list, no matches).
  • Bad initializations (like maxSoFar ← 0 when numbers could be negative).
  • Misreading REPEAT UNTIL logic, leading to incorrect termination behavior.

Procedures, Parameters, Return Values, and Abstraction

A procedure (often called a function) is a named block of code that performs a task. Procedures are executed only when they are called by the main program or another procedure, and they must be defined before they can be used.

Procedures matter because they let you:

• Decompose a large problem into smaller parts
• Reuse code without copying and pasting
• Abstract away details so you can focus on the big picture

Calling a procedure changes the normal sequential flow: when a call occurs, the program pauses at that location, runs the procedure’s code, and when the procedure finishes, control returns to the line where the call occurred.

Procedural abstraction

Procedural abstraction means you can use a procedure without needing to think about how it works internally. Often you only need to know:

• the procedure’s name
• the number/type of parameters
• what output (or effect) to expect

Parameters (arguments): making procedures flexible

A parameter is an input variable to a procedure. When you call the procedure, you pass values as arguments. Parameters make procedures flexible because you can call the same procedure many times with different values.

Return values vs. displaying

A procedure can return a value to the caller. Returning is more flexible than only displaying because the returned value can be stored, combined, or used in a condition.

Example:

PROCEDURE AddTax(price)
  RETURN price * 1.08

final ← AddTax(50)
DISPLAY(final)

A common misunderstanding is thinking that “displaying” a value is the same as “returning” a value:

• Display: outputs to the user
• Return: sends a value back to the code that called the procedure

Also note two important uses of a RETURN statement:

1. It can end a procedure early (no later code in the procedure runs).
2. It can send a value back to the calling code.

Scope (what variables a procedure can see)

Variables created inside a procedure are typically local to that procedure unless the pseudocode indicates otherwise. Do not assume a procedure updates variables outside it unless you see a returned value being stored or a shared data structure being modified.

Worked example: a procedure that counts matches

PROCEDURE CountAtLeast(aList, threshold)
  count ← 0
  FOR EACH x IN aList
    IF x ≥ threshold
      count ← count + 1
  RETURN count

scores ← [50, 70, 90, 70]
DISPLAY(CountAtLeast(scores, 70))

It counts values 70 or higher: 70, 90, 70, so it returns 3.

Built-in procedures you should recognize

Some procedures are built-in (prewritten and tested). You don’t need to know how they are coded internally, only how to use them.

• DISPLAY(value) outputs a value.
• INPUT() accepts data from the user (often from the keyboard). When the program reaches an input statement, it pauses and waits for the user.

Exam Focus

• Typical question patterns:
  • Determine what a procedure returns for given inputs.
  • Choose which procedure best matches a described behavior (including parameters).
  • Identify how procedural abstraction reduces complexity in a larger program.
  • Trace what happens when a procedure is called (control leaves, then returns).
• Common mistakes:
  • Confusing what a procedure displays with what it returns.
  • Forgetting that parameters receive values from the call.
  • Assuming a procedure changes external variables without an explicit return/store or shared structure update.
  • Forgetting that RETURN ends the procedure immediately.

Libraries, APIs, Random Values, and Simulations

A library is a collection of prewritten procedures you can use. Libraries matter because they:

• Reduce development time (don’t reinvent the wheel)
• Increase reliability (library code is often well-tested)
• Enable abstraction (you use the capability without needing internal details)

An API (Application Programming Interface) is a way for programs to interact with other software or libraries. API documentation provides the information needed to set up the interface and use the connected software correctly.

Randomness with RANDOM(a, b)

AP pseudocode includes a random number generator:

• RANDOM(a, b) returns a random integer between a and b, inclusive.

Random number generators are especially useful in games, simulations, and sampling.

A common misconception is expecting random results to look perfectly balanced in small samples. Randomness only guarantees predictable patterns in the long run (for fair settings), not in every short run.

Simulations: modeling the real world

A simulation uses a computer program to imitate a real-world process. Simulations matter because many systems are too expensive, dangerous, slow, or complex to test directly.

General simulation workflow:

1. Define system rules.
2. Use randomness if the real process is probabilistic.
3. Run many trials.
4. Aggregate results to estimate likelihoods or long-term behavior.

Simulations are widely used in engineering and science. For example:

• Street traffic models: used when traffic systems are too complicated to analyze directly. Simulations provide visual demonstrations for different present and future scenarios and help predict vehicle behavior for planning and operation.
• Solar activity / solar system models: simulation tools are part of modern design processes. Models require significant time and effort to develop, and modeling and simulation are powerful methods to evaluate the design of space systems. Simulation models represent valuable knowledge used to build systems that explore space.

Worked example: estimating a probability with repeated trials

Estimate the chance of rolling at least one 6 in four rolls of a die.

trials ← 1000
success ← 0

REPEAT trials TIMES
  gotSix ← false
  REPEAT 4 TIMES
    roll ← RANDOM(1, 6)
    IF roll = 6
      gotSix ← true
  IF gotSix = true
    success ← success + 1

DISPLAY(success / trials)

Increasing trials generally improves the estimate.

Exam Focus

• Typical question patterns:
  • Explain why using a library procedure is beneficial (abstraction, reliability, time).
  • Trace code using RANDOM(a, b) and reason about possible outcomes.
  • Interpret what a simulation is estimating and how changing the number of trials affects results.
  • Recognize that APIs/libraries come with documentation that explains how to use them.
• Common mistakes:
  • Assuming RANDOM(a, b) excludes endpoints (it is inclusive).
  • Confusing a single trial’s outcome with an estimated probability from many trials.
  • Forgetting to reset per-trial variables (like gotSix) inside the outer loop.

Searching, Analyzing Algorithms, and Algorithmic Efficiency

Searching: linear vs. binary

Searching is the task of finding a needed element in a dataset or determining it is not there.

• Linear search (sequential search) checks each record from beginning to end until it finds the target or reaches the end. It works on any list, including unsorted lists.
• Binary search is far more efficient, but the data must be sorted. It is a “divide and conquer” algorithm because it repeatedly divides the search range in half.

A common mistake is trying to apply binary search to unsorted data; without sorted order, you can’t safely eliminate half the remaining elements.

Analyzing algorithms: instances and problem types

• An instance of a problem is a specific example of that problem.
• A decision problem has a yes/no answer.
• An optimization problem asks for the best solution among many possibilities.

Algorithm efficiency (time and space)

Algorithmic efficiency describes the resources an algorithm uses, especially time (how many steps) and space (how much memory). Efficiency becomes crucial with very large datasets, and it’s usually discussed in terms of input size.

Efficiency can be:

• determined by mathematical reasoning/proof, and
• informally measured by running the algorithm on datasets of different sizes and observing time/memory usage.

AP CSP often emphasizes qualitative growth patterns:

• Linear time: work grows proportionally with the number of items (one pass through a list).
• Quadratic time: work grows roughly with the square of the number of items (often from nested loops over the same list).

Worked example: recognizing quadratic behavior

count ← 0
FOR EACH a IN nums
  FOR EACH b IN nums
    IF a < b
      count ← count + 1
DISPLAY(count)

If nums has length n, the inner comparison runs about n * n times, which scales much worse than a single traversal.

Exam Focus

• Typical question patterns:
  • Compare two algorithms and decide which scales better as input size grows.
  • Identify whether an algorithm is more like “check all items” (linear) or “nested checks” (quadratic) from its structure.
  • Explain why binary search requires sorted data.
  • Classify a task as a decision problem vs. an optimization problem.
• Common mistakes:
  • Assuming a faster method (like binary search) works without required conditions (like sorted data).
  • Underestimating nested loops by thinking “it’s just two loops” rather than recognizing multiplicative growth.

Limits of Computation: Hard Problems, Heuristics, and Undecidability

Algorithms have limits. Some problems may be solvable in principle, but we may not have algorithms efficient enough to solve them in a reasonable amount of time with current technology—especially at large scales.

Heuristic approaches (practical but not guaranteed optimal)

A heuristic approach is a method that may not produce the optimal or best possible solution, but produces a result that is “good enough” to be useful. Heuristics are common when exact solutions are too slow or too resource-intensive.

Decidable vs. undecidable (unsolvable) problems

A decidable problem is one where an algorithm can be written that produces a correct yes/no answer for all possible inputs. Example: determining whether a number is prime (there are algorithms that can always answer correctly).

An undecidable problem is one for which no algorithm can give a correct yes/no answer for all cases.

A classic undecidable problem is the Halting Problem: determining, for every possible program and input, whether the program will eventually stop or run forever. The key implication is that there are fundamental logical limits to computation. This is not just “too hard right now”; it’s impossible to solve in general for all cases.

Exam Focus

• Typical question patterns:
  • Explain why some problems cannot be solved by any algorithm for all inputs (undecidability concept).
  • Distinguish between “computationally expensive” (may be possible but impractical) and “undecidable” (impossible in general).
  • Explain what a heuristic is and why it might be used.
• Common mistakes:
  • Thinking undecidable means “too hard in practice” rather than “impossible to solve for all inputs.”
  • Treating “no efficient algorithm known” as the same thing as “no algorithm exists.”