Algorithms & Programming

What this unit covers

The topics below follow the published CS Principles course framework for Unit 3. This unit is worth 30–35% of the exam, so budget your time against that rather than against how long the unit takes to teach.

Lessons in this unit

• Variables, Assignment & Expressions13 min · 3 objectivesExplain what a variable is and how assignment stores a value · Trace how variable values change as statements execute · Evaluate arithmetic expressions including MOD
• Procedures & Abstraction14 min · 3 objectivesDefine a procedure with parameters and call it with arguments · Explain how procedures use abstraction to manage complexity · Trace a program that returns and uses a value from a procedure
• Lists & Iteration14 min · 3 objectivesAccess and modify list elements using 1-based indexing · Use FOR EACH and indexed loops to process every element · Trace list operations such as APPEND, INSERT, and REMOVE
• Simulation & Randomness12 min · 3 objectivesExplain what a simulation is and why simulations are useful · Describe the trade-offs between a simulation and the real experiment · Use RANDOM to model chance in a program

Formulas in Unit 3

Every term in Unit 3

All 56 terms we publish for Algorithms & Programming, with definitions. Reading them through is the fastest way to find the ones you cannot define — then drill those in cram mode until you can produce them without the prompt.

Heuristic

An approach to a problem that produces a solution that is "good enough" when an exact solution would take an unreasonable amount of time (e.g., Traveling Salesperson).

Algorithm

A finite set of instructions that accomplishes a task. Every algorithm can be built from sequencing, selection and iteration alone.

Sequencing

Executing statements in the order they are written. The default control flow, and the first of the three constructs.

Selection

Choosing between paths based on a condition — IF / ELSE. The second construct.

Iteration

Repeating a block of statements — REPEAT n TIMES, REPEAT UNTIL, or FOR EACH. The third construct.

Variable

A named reference to a value stored in memory. The name is an abstraction; the value can change while the name does not.

Assignment in AP pseudocode

a ← expression. The arrow evaluates the right side and stores it in the variable on the left. It is not a claim of equality.

DISPLAY

Pseudocode output: DISPLAY(expression) shows the value followed by a space. Multiple DISPLAY calls run onto one line.

INPUT in AP pseudocode

INPUT() accepts a value from the user and evaluates to it, usually assigned to a variable: name ← INPUT().

MOD

a MOD b is the remainder after dividing a by b. n MOD 2 = 0 tests for even, and MOD is the standard way to test divisibility on this exam.

List indexing in AP pseudocode

Lists are indexed starting at 1, not 0. aList[1] is the first element. Exam questions rely on this, and it differs from most real languages.

LENGTH

LENGTH(aList) evaluates to the number of elements in the list. aList[LENGTH(aList)] is the last element.

INSERT

INSERT(aList, i, value) puts value at index i and shifts everything from i onward one position to the right. The list grows by one.

APPEND

APPEND(aList, value) adds value to the end of the list, increasing its length by one.

REMOVE

REMOVE(aList, i) deletes the element at index i and shifts everything after it left. The list shrinks by one — which is why removing while looping forward skips elements.

FOR EACH loop

FOR EACH item IN aList repeats once per element, with item taking each value in order. You cannot change the list length safely inside it.

REPEAT UNTIL

REPEAT UNTIL (condition) tests the condition BEFORE each pass and stops when it becomes true. If the condition is already true, the body never runs.

REPEAT n TIMES

Runs the body exactly n times, where n is evaluated once at the start. Changing n inside the loop does not change how many times it runs.

Infinite loop

A loop whose stopping condition never becomes true. Usually because the variable in the condition is never updated inside the body.

Off-by-one error

Looping one time too many or too few, or starting at the wrong index. The commonest logic error, and why exam questions test the first and last elements.

Boolean value

true or false. Conditions evaluate to a Boolean, and Boolean variables can store the result of a comparison.

Relational operators

=, ≠, >, <, ≥, ≤. They compare two values and produce a Boolean.

AND

true only when both operands are true. Narrows a condition.

OR

true when at least one operand is true, including both. Widens a condition.

NOT

Reverses a Boolean. NOT (a > b) is equivalent to a ≤ b — note that it includes equality.

Negating a compound condition

NOT (A AND B) is (NOT A) OR (NOT B); NOT (A OR B) is (NOT A) AND (NOT B). Getting the operator swap wrong is a standard trap.

Nested conditional

An IF inside another IF. Equivalent to an AND when both must hold, but different when the outer branch has an ELSE.

Procedure

A named group of statements — also called a function or method. Called by name, and the code inside runs.

Parameter vs argument

A parameter is the name in the procedure definition. An argument is the actual value passed in when it is called.

RETURN

Ends a procedure and sends a value back to the caller. A procedure with RETURN can be used inside an expression; one without cannot.

Procedural abstraction

Giving a named procedure to a block of code so it can be used without knowing how it works. Reduces complexity and makes the program easier to change.

Why procedures reduce complexity

They let the reader think about what a segment does rather than how, and a change to the implementation happens in one place instead of many.

Student-developed procedure

For the Create task, a procedure you wrote yourself that takes at least one parameter affecting its behavior, and includes sequencing, selection and iteration. A procedure ignoring its parameter does not qualify.

Library

A collection of procedures that can be used in other programs. Using one is a form of abstraction, and it must be acknowledged.

API

Application program interface — the specification of how to use a library's procedures: their names, parameters and what they return. Documentation of the abstraction, not of the implementation.

Linear search

Check each element in turn until the target is found or the list ends. Works on any list, sorted or not.

Binary search

Repeatedly halve a SORTED list, discarding the half that cannot contain the target. Far faster than linear search, and incorrect on an unsorted list.

Why binary search needs a sorted list

It decides which half to discard by comparing with the middle element. Without ordering, that comparison tells you nothing about where the target is.

Comparing linear and binary search

Linear search checks up to n elements; binary search checks about log₂n. For a million items that is a million versus twenty.

Reasonable time

An algorithm runs in reasonable time if its steps grow polynomially with input size. Exponential or factorial growth is not reasonable, however fast the computer.

Undecidable problem

A problem for which no algorithm can give a correct yes-or-no answer for every possible input. Not merely slow — impossible in principle.

Decidable vs undecidable

A decidable problem has an algorithm that always produces a correct answer. Undecidability is about existence of any such algorithm, not about running time.

Simulation

A program modeling a real phenomenon, using simplifying assumptions. Cheaper, safer and faster than the real thing, and only as good as its assumptions.

Why simulations use random values

To model variability the real system has. Running a simulation many times with random inputs gives a distribution of outcomes rather than a single answer.

RANDOM

RANDOM(a, b) evaluates to a random integer from a to b inclusive. Both endpoints are possible — the count of outcomes is b − a + 1.

Limitations of simulations

They omit detail by design, so results depend on which details were dropped. A simulation can be internally correct and still wrong about the world.

Sequential computing

Operations run one after another, one at a time. The baseline every other model is compared against.

Parallel computing

Some operations run at the same time on different processors. Reduces total time when work can be split.

Distributed computing

Multiple devices work on a single problem across a network. Enables problems too big for one machine, at the cost of coordination.

Speedup

Sequential run time divided by parallel run time. If a task takes 60 seconds sequentially and 20 in parallel, the speedup is 3.

Why speedup is limited

The portion that must run sequentially sets a floor. Adding processors cannot shorten work that cannot be split, so speedup never equals the number of processors.

Calculating parallel run time

The parallel portion is divided among processors and the sequential portion is added on unchanged. Work the sequential part out first — it is where the marks are.

Program state

The values of all variables at a moment during execution. Hand-tracing is the act of tracking state line by line.

Concatenation

Joining strings end to end. In AP pseudocode this is usually shown by displaying values in sequence rather than by an operator.

Robust program

One that behaves sensibly on unexpected input rather than crashing. Checking input before using it is the main technique.

Efficiency of an algorithm

How its resource use grows with input size. On this exam, compared informally — "roughly doubles", "roughly squares" — rather than with formal notation.

What examiners penalize here

• `MOD` returns the *remainder*, not the quotient. Keep the classic uses ready: `n MOD 2 = 0` tests even, and `n MOD b = 0` tests whether b divides n evenly.
• The exam frames procedures around **abstraction** and **reuse** (managing complexity), not speed. Know the vocabulary precisely: a *parameter* is in the definition, an *argument* is the value you pass in the call.
• On list-tracing questions, redraw the list after **every** INSERT or REMOVE, because those operations shift the positions of all later elements. Track indices carefully — the exam builds traps out of these shifts.
• `RANDOM(a, b)` is **inclusive** of both endpoints. To model n equally likely outcomes numbered 1 to n, use `RANDOM(1, n)`. Off-by-one endpoints are a favorite exam distractor.

Practice CS Principles

Our practice bank is drawn from across the whole course rather than filtered to one unit, which is closer to how the exam asks anyway — it will not tell you which unit a question is testing.

Questions about this unit

All 5 units of AP Computer Science Principles

1. Unit 1 · Creative Development
2. Unit 2 · Data
3. Unit 3 · Algorithms & Programming
4. Unit 4 · Computer Systems & Networks
5. Unit 5 · Impact of Computing