Big Idea 3: Algorithms and Programming

Program

A precise set of instructions that a computer can execute.

Algorithm

A step-by-step process for solving a problem or accomplishing a task; the “recipe” behind a solution.

Module

A section of code that can work independently or be combined with other code to build a program.

AP pseudocode

A standardized, language-neutral code style used on the AP CSP exam to test reading, tracing, and algorithm reasoning (not specific language punctuation).

Sequencing

A control structure where statements execute in the order they appear.

Selection

A control structure where the program chooses between paths based on a condition (e.g., IF/ELSE).

Iteration

A control structure where the program repeats a block of statements (loops).

Assignment (←)

An instruction that stores a value into a variable (e.g., x ← expression); it updates stored state and is not a symmetric math equation.

State (program state)

The current stored values of variables and data; assignment changes the program’s state.

Equality test (=)

A comparison used in conditions to check whether two values are equal (e.g., IF x = 5).

1-indexing

List indexing where the first element is at index 1 (AP pseudocode lists are 1-based, not 0-based).

Variable

A named storage location (placeholder) for a value a program needs, such as input, totals, counts, or intermediate results.

Abstraction

A way to manage complexity by using a simplified representation (like a variable or procedure) without needing low-level storage details.

Data type

A category of values (e.g., numbers, booleans, strings, lists) that affects what operations are meaningful.

Boolean

A value that is either true or false; used for decisions and conditions.

String

Text data: a series of characters in quotation marks; digits inside a string are treated as text, not numbers.

Concatenation

Joining strings together to form a longer string.

List

An ordered collection of elements (items) used to store and work with multiple related values.

MOD

An operator that returns the remainder from division (a MOD b); often used for even/odd checks and repeating patterns.

LENGTH(list)

A built-in operation that returns the number of elements in a list; used to determine valid indices and loop bounds.

INSERT

A list operation that inserts an element at a specific position, shifting elements to the right.

APPEND

A list operation that adds an element to the end of a list, increasing the list size by one.

REMOVE

A list operation that deletes an element at a position, shifting remaining elements left and decreasing list size by one.

List traversal

Visiting list elements in a systematic way (often first to last) to compute totals, find max/min, filter, search, etc.

FOR EACH loop

A traversal pattern that runs once per element, assigning each element’s value to an iteration variable in turn.

Accumulator

A variable (like sum or count) that is updated repeatedly during a loop to build a running total or other aggregate.

Filtering

Building a new list by keeping only elements that meet a condition (often using APPEND), instead of removing while iterating.

Linear search

A search method that checks each element from start to end until the target is found or the list ends; works on unsorted data.

Binary search

A faster search method that repeatedly halves the search range; requires the data to be sorted.

Divide and conquer

A strategy that solves a problem by repeatedly splitting it into smaller parts; binary search uses this by halving the search space.

Procedure

A named block of code (function) that performs a task and runs only when called; supports decomposition and reuse.

Parameter

An input variable in a procedure definition that receives a value when the procedure is called.

Argument

The actual value passed into a procedure when it is called (the value that fills a parameter).

Return value

A value sent back from a procedure to the caller; more flexible than DISPLAY because it can be stored or used in expressions/conditions.

Scope (local variables)

The region where a variable can be accessed; variables created inside a procedure are typically local unless a shared structure is modified or a value is returned and stored.

Library

A collection of prewritten procedures you can use to save time, improve reliability, and support abstraction.

API (Application Programming Interface)

A defined way for programs to interact with a library or other software; specifies how to request and use its functionality.

RANDOM(a, b)

A built-in operation that returns a random integer from a to b inclusive; used in games, sampling, and simulations.

Simulation

A program that models a real-world process, often using randomness and many trials to estimate behavior or probabilities.

Algorithmic efficiency

How many resources an algorithm uses—especially time (steps) and space (memory)—as input size grows.

Linear time

Efficiency where work grows proportionally with the number of items (often a single pass through a list).

Quadratic time

Efficiency where work grows roughly with the square of the number of items (often from nested loops over the same data).

Nested loops

A loop inside another loop; commonly causes multiplicative growth in operations (often leading to quadratic behavior).

Instance (problem instance)

A specific example of a problem with particular inputs (one concrete case of the general problem).

Decision problem

A problem type where the output is a yes/no answer.

Optimization problem

A problem type that asks for the best solution among many possibilities (e.g., shortest route).

Heuristic approach

A practical method that produces a good-enough solution but is not guaranteed to be optimal.

Decidable problem

A problem for which an algorithm can be written that correctly answers yes/no for all possible inputs.

Undecidable problem

A problem for which no algorithm can correctly answer yes/no for all possible inputs.

Halting Problem

A classic undecidable problem: determining for every program and input whether the program will eventually stop or run forever.