Glossary

Every term the course defines, with the lesson that introduces it.

A

accumulator: A variable that carries a running result forward through a loop, updated once per item.
Introduced in M2.4 Accumulator patterns
adjacency list: A way to store a graph as a list or dictionary that maps each vertex to the list of its neighbours.
Introduced in M4.12 Graphs and adjacency lists
algorithm: A precise, step-by-step method for solving a problem.
aliasing: Two names that refer to the exact same list or other mutable value, so a change made through one name shows up when the other is read.
Introduced in M2.8 Debugging
assignment: Storing a value under a variable name using the equals sign.
Introduced in M1.1 Values, types, variables and print
augmented assignment: A shorthand such as += that updates a variable using its own current value in one step.
Introduced in M1.2 Integer arithmetic and operators

B

Back edge: An edge in a DFS that points to an ancestor in the DFS tree. Back edges indicate cycles in a directed graph.
Introduced in M6.4 DFS tree properties and edge classification
boolean operator: An operator that combines or inverts boolean values, such as and, or, and not.
Introduced in M1.4 Booleans and conditionals
breadth-first search: A graph traversal algorithm that explores vertices level by level in order of distance from the source.
Introduced in M4.13 BFS and flood fill (iterative)
brute force: Solving a problem by checking every candidate answer directly, with no shortcut.
Introduced in M2.5 Brute force and complete search

C

call stack: The stack of frames for every function call currently in progress, most recent on top.
Introduced in M1.14 Recursion fundamentals
ceiling division: Division that rounds a result up to the next whole number when there is a remainder, computed as -(-a // b).
Introduced in M1.12 Floats, precision and big integers
circular array: An array whose index wraps from the last element back to the first, usually with the modulo operator.
Introduced in M4.15 Circular arrays and wraparound
comparison operator: An operator that compares two values and gives back a boolean, such as ==, <, or in.
Introduced in M1.4 Booleans and conditionals
conditional expression: A one-line either/or expression of the form a if condition else b, which evaluates to a or b depending on the condition.
Introduced in M1.4 Booleans and conditionals
coordinate compression: Mapping large coordinate values to small ranks to enable dense array storage for sparse 2D problems.
Introduced in M6.8 Coordinate compression and sweep line

D

difference array: An array storing the differences between consecutive elements, used to apply multiple range updates in O(1) time per update.
Introduced in M4.4 Difference arrays and interval clamping
Dijkstra's algorithm: An algorithm that finds the shortest path from a start node to all other nodes in a graph with non-negative edge weights.
Introduced in M6.1 Dijkstra's shortest paths
disjoint set union: A data structure that tracks which elements belong to the same group, supporting fast union and connectivity queries.
Introduced in M5.10 Disjoint Set Union (union-find)
double-ended queue (deque): A data structure that supports efficient insertion and removal at both ends, useful for sliding window problems.
Introduced in M5.11 Heaps and lazy deletion; ordered-set substitutes

E

edge: A connection between two vertices in a graph, sometimes carrying a weight.
Introduced in M4.12 Graphs and adjacency lists
edge case: An input at the extreme or unusual end of what a problem's bounds allow, such as the smallest size, every value equal, or a tie.
Introduced in M2.6 Case analysis and edge cases

F

flood fill: An algorithm that identifies and visits all connected cells matching a condition in a 2D grid.
Introduced in M4.13 BFS and flood fill (iterative)
floor division: Division that rounds the exact answer down to a whole number, written //.
Introduced in M1.2 Integer arithmetic and operators

G

generator expression: The same shape as a list comprehension without square brackets, producing values one at a time instead of building a whole list.
Introduced in M1.8 Lists (1D and 2D)
greedy algorithm: An algorithm that solves a problem by making locally optimal choices at each step without reconsidering earlier decisions.
Introduced in M4.2 Sorting with keys and greedy
greedy choice property: A property of optimization problems where a globally optimal solution always includes a locally optimal (greedy) choice made at the first step.
Introduced in M4.2 Sorting with keys and greedy

H

hash collision: Two different inputs that produce the same hash value. Rare with a good hash and a large modulus, but never impossible.
Introduced in M5.4 Polynomial rolling hash

I

interpreter: The program that reads Python source code and runs it, one instruction at a time.
Introduced in M0.1 What a program is
Interval DP: A dynamic programming technique where subproblems are defined on contiguous intervals of a sequence, solved bottom-up by increasing interval length.
Introduced in M6.6 Interval DP and O(n³) algorithms
invariant: A property or quantity that remains unchanged through a series of operations or transformations.
Introduced in M4.5 Mathematical insight

L

lazy deletion: An optimization technique where items are marked invalid instead of being removed immediately, with removal deferred until they are popped.
Introduced in M5.11 Heaps and lazy deletion; ordered-set substitutes
list comprehension: A one-line way to build a list from an existing sequence, written [expression for name in sequence], optionally filtered with if.
Introduced in M1.8 Lists (1D and 2D)
local: A variable that exists only inside the function call that created it, separate from any variable of the same name outside that function.
Introduced in M1.10 Functions and scope

M

memoization: Storing the result of each distinct call to a recursive function the first time it runs, so a later call with the same arguments is looked up instead of recomputed.
Introduced in M4.11 Memoization and introductory dynamic programming
method: A function called on a value using a dot, such as .split() called on a string.
Introduced in M1.3 Reading input
Minimum spanning tree: A spanning tree of a graph with the smallest total edge weight. Connects all nodes using the fewest or cheapest edges.
Introduced in M6.3 Minimum spanning tree and Kruskal with DSU
modulo: The remainder left over after floor division, written %.
Introduced in M1.2 Integer arithmetic and operators
monotonic deque: A double-ended queue maintaining elements in monotonic order to track sliding window maximum.
Introduced in M6.11 Monotonic stack and deque
monotonic stack: A stack storing elements in monotonic order, used to efficiently find the next greater element.
Introduced in M6.11 Monotonic stack and deque
multiple assignment: Assigning several values to several names in one line, matched left to right by position.
Introduced in M1.3 Reading input

O

operator: A symbol such as + or // that performs a computation on one or more values.
Introduced in M1.2 Integer arithmetic and operators

P

path halving: An optimization in the find operation where each node points to its grandparent instead of its parent, flattening the tree over time.
Introduced in M5.10 Disjoint Set Union (union-find)
precedence: The fixed order in which Python runs the operators in a line that has more than one. Parentheses change that order.
Introduced in M1.2 Integer arithmetic and operators
prefix sum: An array where each element stores the cumulative sum of all elements up to that index, enabling O(1) range-sum queries.
Introduced in M4.3 Prefix sums
priority queue: A data structure that retrieves the item with the smallest (or largest) priority key first.
Introduced in M6.1 Dijkstra's shortest paths

Q

queue: A first-in, first-out data structure where elements are added at the back and removed from the front.
Introduced in M4.13 BFS and flood fill (iterative)

R

reassignment: Binding an existing variable name to a new value.
Introduced in M1.1 Values, types, variables and print
recursion: A function calling itself to solve a smaller version of the same problem.
Introduced in M1.14 Recursion fundamentals

S

segment tree: A tree data structure that stores partial answers about ranges, enabling point updates and range queries in logarithmic time.
Introduced in M7.1 Segment tree structure and custom merges
simulation: Solving a problem by running its described process step by step, with a variable for each piece of state.
Introduced in M2.3 Simulation
source code: The plain text you write that describes what you want a program to do, before anything runs it.
Introduced in M0.1 What a program is
sparse table: A precomputed table for answering idempotent range queries (minimum, maximum, gcd) in constant time after O(N log N) preprocessing.
Introduced in M7.3 Sparse table for fast range queries
Sparsification: The process of reducing a graph or state space by keeping only the nodes and edges that can actually be reached or are needed to solve the problem, discarding theoretical possibilities that never arise in practice.
Introduced in M6.2 State-space graph modelling and sparsification
standard input: The stream of text a program reads its input from, normally whatever the judge feeds it.
Introduced in M0.4 The standard input/output model and exact output
standard library: The collection of modules that ships with Python itself, without installing anything extra.
Introduced in M1.13 Imports and the standard library tour
standard output: The stream of text a program writes its output to, normally what the judge reads and compares.
Introduced in M0.4 The standard input/output model and exact output
subtask: A named group of hidden test cases within one problem, run and reported together as a batch.
Introduced in M0.5 How judging works

T

traceback: The message Python prints when a program stops with an error, naming the file, the line, and the error itself.
Introduced in M0.6 Reading error messages
Tree edge: An edge in a DFS that leads to a node being visited for the first time. Tree edges form the DFS tree.
Introduced in M6.4 DFS tree properties and edge classification
true division: Division written with / that always produces a float, even when the numbers divide evenly.
Introduced in M1.2 Integer arithmetic and operators
type: The classification of a value, such as an integer, string, or boolean, that determines what operations it supports.
Introduced in M1.1 Values, types, variables and print

U

union by size: An optimization where the smaller tree is always attached under the larger tree during union, keeping the forest shallow.
Introduced in M5.10 Disjoint Set Union (union-find)
union-find: Another name for disjoint set union; commonly used when describing the find and union operations.
Introduced in M5.10 Disjoint Set Union (union-find)

V

variable: A name that refers to a value stored while a program runs.
Introduced in M1.1 Values, types, variables and print
verdict: The judge's recorded result for one test case, such as accepted or wrong answer.
Introduced in M0.5 How judging works
vertex: A single node in a graph; the thing that edges connect.
Introduced in M4.12 Graphs and adjacency lists

W

walrus operator: The := operator, which assigns a value to a name inside a larger expression instead of on its own line.
Introduced in M1.15 The Python 3.8 language boundary