Source: AP Computer Science Principles Course Framework
Tags: procedure, function, parameter, argument, return, procedural abstraction, algorithm, sequencing, selection, iteration, loop, for loop, while loop, infinite loop, repeat until, MOD, modulo, PEMDAS, simulation, heuristic, algorithmic efficiency, polynomial, exponential, decidable, undecidable, halting problem
Difficulty: Intermediate to Advanced Prerequisites: Big Idea 3 Part 1 (variables, data types, lists, Boolean logic).
This second half of Big Idea 3 covers procedures (functions), loops, algorithm design, simulations, and algorithmic efficiency. Together with Part 1, this unit makes up 35% of the exam. Procedures let you reuse code and break problems into smaller parts. Loops let you repeat actions without rewriting code. The MOD operator and PEMDAS are tested directly. Algorithmic efficiency distinguishes problems that computers can solve in a reasonable time (polynomial) from those they cannot (exponential or factorial). You also need to know the difference between decidable and undecidable problems, with the halting problem as the classic example.
Procedures group instructions for reuse and take parameters as input. Algorithms are built from three structures: sequencing, selection (IF/ELSE), and iteration (loops). The MOD operator gives the remainder of division. Efficiency matters because some algorithms run in reasonable time (polynomial) and others do not (exponential). Some problems, like the halting problem, are undecidable and cannot be solved by any algorithm for all cases.
Procedure (function, method)
A named group of programming instructions that can be called (invoked) to execute those instructions. Lets you reuse the same code without rewriting it.
Parameter
An input variable defined in a procedure's declaration. It acts as a placeholder for the value that will be passed in when the procedure is called.
Argument
The actual value passed into a procedure when it is called. If the procedure is add(x, y) and you call add(3, 5), then 3 and 5 are the arguments.
Return statement
Specifies the value a function sends back to the code that called it. A return statement also terminates the procedure immediately. In simple terms, it is the answer the function gives back.
Procedural abstraction
Using procedures to break a large problem into smaller subproblems. Each procedure handles one piece, simplifying the code and improving readability. You do not need to know how a procedure works internally to use it.
Algorithm
A set of instructions used to accomplish a specific task or solve a problem. Expressed through sequencing, selection, and iteration.
Sequencing
Steps that execute in order, one after another. The default flow of a program.
Selection
Making a decision based on a condition (IF/ELSE). The program chooses between different paths of execution.
Iteration (loop)
Repeating a set of instructions until a condition is met. Lets programs perform tasks repeatedly without duplicating code.
REPEAT n TIMES loop
Executes a block of code exactly n times. You know in advance how many repetitions will occur.
REPEAT UNTIL(condition) loop
Repeats a block of code until a Boolean condition evaluates to true. The number of iterations depends on when the condition is met.
While loop
Runs while a condition is true, and stops when the condition becomes false. Checks the condition before each iteration. You may not know in advance how many times it will run. Three parts: initialise a counter, a Boolean expression, and a statement that changes the counter.
For loop
A loop with a built-in counter: for (var i = 0; i < 4; i++). You know how many times it will execute.
Infinite loop
A loop that repeats indefinitely because the controlling condition is always true or there is no condition at all. This is a bug unless intentional.
MOD (modulo) operator
Returns the remainder when one integer is divided by another. a MOD b divides a by b and gives back the remainder. Example: 27 MOD 4 = 3 (because 27 / 4 = 6 remainder 3).
RANDOM(a, b)
Generates and returns a random integer from a to b, inclusive. Each result is equally likely.
Simulation
The process of creating a model or representation of a real-world system on a computer. Simulations are a form of abstraction: they simplify reality to investigate questions without real-world complications.
Heuristic
An approximate solution used when a problem cannot be solved exactly in a reasonable amount of time. It gives a "good enough" answer rather than the perfect one.
Algorithmic efficiency
An estimate of how many computational resources (time, memory, steps) an algorithm uses. In simple terms, how many steps it takes to finish as the input grows.
Polynomial efficiency (reasonable time)
Algorithms whose step count grows as a polynomial function of the input size (e.g. n, n^2, log n). These are considered to run in a reasonable amount of time.
Exponential / factorial efficiency (unreasonable time)
Algorithms whose step count grows as an exponential or factorial function of the input size (e.g. 2^n, n!). These become impractical very quickly as input grows.
Decision problem
A problem with a yes or no answer.
Optimisation problem
A problem that seeks the best possible answer (e.g. the shortest path between two cities).
Decidable problem
A decision problem for which an algorithm can be written that always produces a correct yes or no answer for every possible input.
Undecidable problem
A problem for which no algorithm can be written that always provides a correct yes or no answer for every possible input. May be solvable for some cases, but not all.
Halting problem
A famous undecidable problem posed by Alan Turing. It asks whether a general algorithm can determine, for any arbitrary program and input, whether that program will eventually stop running. Turing proved no such algorithm exists.
A procedure groups instructions under a name so you can call them repeatedly
Parameters are the input variables in the procedure definition
Arguments are the actual values you pass in when calling the procedure
Not every procedure requires parameters
A return statement sends a value back to the caller and terminates the procedure
Procedural abstraction means you can use a procedure without understanding its internal code
Example of procedural abstraction, replacing repeated code:
PROCEDURE summing_machine(first_number, second_number)
{
sum_value = first_number + second_number
DISPLAY(sum_value)
}
summing_machine(5, 7)
summing_machine(8, 2)
summing_machine(9, 3)
This replaces three separate blocks of nearly identical code.
Every algorithm is built from three structures:
Sequencing: instructions run in order
Selection: IF/ELSE decides which path to take
Iteration: loops repeat instructions
These three structures can be combined to solve any computable problem
REPEAT n TIMES: runs exactly n times
REPEAT UNTIL(condition): runs until the condition becomes true
While loop: runs while the condition is true, checks before each iteration
Three parts: (1) initialise counter, (2) Boolean check, (3) update counter
while (i < 10) { ... i = i + 1 }
For loop: compact version with built-in counter: for (var i = 0; i < 4; i++)
Infinite loop: the condition never becomes false (or there is no condition). Usually a bug.
Arithmetic operators: +, -, *, /
Standard order of operations (PEMDAS) applies
MOD gives the remainder: 17 MOD 5 = 2, 27 MOD 4 = 3
MOD has the same precedence as * and /
MOD is useful for checking divisibility (if n MOD 2 = 0, then n is even)
Existing algorithms you should recognise: finding max/min values, calculating sums and averages, sorting a list, compressing data, finding a robot's path through a maze
You can combine and modify existing algorithms to create new ones
RANDOM(a, b) generates a random integer from a to b inclusive
Model real-world phenomena on a computer
A form of abstraction: they simplify reality
Used to predict, plan, and investigate without real-world constraints
Disadvantages: may include bias from what the creator chose to include or exclude, and may be out of scale
Efficiency measures how many steps an algorithm takes as input size grows
Reasonable time (polynomial): n, n^2, log n. These scale manageably.
Unreasonable time (exponential/factorial): 2^n, n!. These become impractical very quickly.
Example: with n bits, a brute-force check of all combinations requires 2^n checks
When finding the max number of list elements a binary approach handles, find the closest power of 2 (e.g. for 200 elements, 2^8 = 256 is closest)
A decidable problem has an algorithm that always gives a correct yes/no answer for all inputs
An undecidable problem has no such algorithm. It may be solvable for specific cases, but no algorithm solves every case.
The halting problem (Turing): can an algorithm determine whether any given program will eventually stop running? Turing proved the answer is no. Some programs loop forever, and no general algorithm can detect this for all possible programs.
a MOD b = remainder of a / b
PEMDAS applies to all expressions
RANDOM(a, b) = random integer from a to b inclusive
Reasonable time: polynomial (n^2, n log n, etc.)
Unreasonable time: exponential (2^n) or factorial (n!)
Weather forecasting uses simulations to model atmospheric conditions. The models are abstractions: they cannot capture every molecule, but they are useful enough to predict tomorrow's rain.
Route-finding apps (like GPS navigation) solve optimisation problems using heuristics, because checking every possible route between two cities would take unreasonable time for large road networks.
Students often think a return statement just displays a value. It does not. It sends a value back to wherever the procedure was called, and it immediately ends the procedure.
Students confuse parameters and arguments. Parameters are the variable names in the procedure definition. Arguments are the actual values passed in during a call.
Students sometimes believe MOD gives the quotient. It gives the remainder. 17 MOD 5 = 2 (not 3).
Students assume all problems can be solved with an algorithm given enough time. Undecidable problems cannot be solved by any algorithm for all possible inputs, regardless of time.
⚠️ Tracing through loops (especially nested loops and loops that modify lists) is a very common exam question. Use scratch paper and track each variable's value on every iteration.
⚠️ MOD questions appear regularly. Be comfortable calculating remainders.
⚠️ Know the difference between parameters and arguments, and between procedures that return values and those that do not.
⚠️ Reasonable vs. unreasonable time: be able to classify an algorithm's efficiency from its description or growth rate.
⚠️ The halting problem is the go-to example of an undecidable problem. Know what it asks and why it cannot be solved.
⚠️ Robot questions on the exam use algorithms with sequencing, selection, and iteration. These are time-consuming, so save extra time for them.
Fill in the blank: The __________ operator returns the remainder of integer division.
True or False: A procedure must always have at least one parameter.
Fill in the blank: An algorithm that runs in 2^n time is considered to run in __________ time.
True or False: The halting problem is a decidable problem.
Fill in the blank: A REPEAT UNTIL loop checks whether the condition is __________ before stopping.
Answers: 1. MOD (modulo). 2. False (procedures can have zero parameters). 3. Unreasonable (exponential). 4. False (it is undecidable). 5. True.
Q: What is the output of this code? x ← 1 REPEAT 4 TIMES { x ← x * 2 } DISPLAY(x)
A: 16. The loop doubles x four times: 1 → 2 → 4 → 8 → 16.
Q: What is the value of 100 MOD 7?
A: 2. 100 / 7 = 14 remainder 2.
Q: A procedure is defined as PROCEDURE greet(name) { RETURN("Hello " + name) }. What does greet("Alice") return?
A: The string "Hello Alice". The argument "Alice" is passed to the parameter name, concatenated with "Hello ", and the result is returned.
Q: Explain why the halting problem is undecidable.
A: The halting problem asks whether an algorithm can be written that determines, for any program and any input, whether that program will eventually stop running. Turing proved that no such universal algorithm exists. You can solve the problem for specific programs, but no single algorithm handles every possible case.
Q: An algorithm takes 3 seconds for 10 items, 12 seconds for 20 items, and 48 seconds for 40 items. Is this more likely polynomial or exponential growth?
A: This is likely polynomial. The time roughly quadruples when the input doubles, which is consistent with n^2 growth (quadratic). Exponential growth would be far more dramatic (e.g. 3 seconds for 10 items would become thousands of seconds for 40 items if it were 2^n).
Procedural abstraction connects to data abstraction in Big Idea 2 (both involve hiding complexity to focus on what matters).
Algorithmic efficiency connects to Big Idea 4 (Computer Systems and Networks), where parallel computing reduces execution time by splitting work across multiple processors.
Simulations connect to Big Idea 5 (Impact of Computing), where computing bias can be introduced through the choices a simulation's creator makes.
procedure, function, method, parameter, argument, return statement, procedural abstraction, algorithm, sequencing, selection, iteration, loop, for loop, while loop, REPEAT, REPEAT UNTIL, infinite loop, MOD, modulo, remainder, PEMDAS, order of operations, RANDOM, simulation, abstraction, heuristic, algorithmic efficiency, reasonable time, unreasonable time, polynomial, exponential, factorial, decision problem, optimisation problem, decidable, undecidable, halting problem, Alan Turing, AP CSP, AP Computer Science Principles, Big Idea 3