Glossary

Every technical word this roadmap uses, in alphabetical order. Each definition is written without relying on other jargon, so you can start anywhere. 84 terms.

adjacency list: A way of storing a graph: for each thing, keep a list of what it connects to. Compact when most things are not connected to most other things.
algorithm: A set of steps for getting something done, written precisely enough that a computer can follow it without guessing.; A recipe. “Beat two eggs, then add flour” is an algorithm; “make it taste nice” is not, because the steps are not specific.
amortised: The average cost per operation over a long run, when most operations are cheap but occasionally one is expensive. The rare expensive one gets spread across all the cheap ones.; Most days you just add shopping to the cupboard, which is quick. Occasionally the cupboard is full and you buy a bigger one, which is slow. Averaged out, it is still quick.
array: A block of memory holding items one after another with no gaps, which is exactly why reaching any position is instant.
attribute: A piece of information stored inside an object, such as a bank account’s balance.
backtracking: Trying a possibility, and the moment it clearly cannot work, abandoning it and stepping back to try a different one.; Solving a maze by walking down a corridor and reversing out the moment you hit a dead end.
balanced: A tree is balanced when its branches are roughly equal in depth. An unbalanced tree degenerates into a long chain and loses all its speed advantage.
base case: The stopping rule in a recursive function — the simplest situation, where it answers directly instead of calling itself again. Without one, the program never stops.
Big-O notation: A shorthand for how much slower something gets as the amount of data grows. It ignores exact timings and hardware, and describes the shape of the growth instead.; Describing a journey as “twice as long if the distance doubles” rather than “43 minutes”. Useful because it stays true on any machine.
binary search: Finding something in sorted data by repeatedly checking the middle and throwing away the half it cannot possibly be in.
binary search tree: A binary tree kept in sorted order: everything smaller goes left, everything larger goes right. That single rule is what makes searching it fast.
binary tree: A tree where every node has at most two children, usually called left and right.
bit: The smallest piece of information a computer holds — a single 0 or 1. Everything else is built out of these.
breadth-first search: Exploring a graph in rings: everything one step away, then everything two steps away, and so on. Finds the shortest route when every step costs the same.
breakpoint: A marker you place on a line telling the program to pause there, so you can inspect every value before letting it continue.
brute force: Trying every possibility with no cleverness at all. Usually too slow to ship, but the easiest way to be certain of the right answer.
cache: A small, fast store of answers you have already worked out or fetched, kept so you do not have to do the slow work twice.
call stack: The computer’s running list of which functions are part-finished and waiting. Every call adds to the pile; every finish removes one.; A stack of unfinished paperwork. You can only work on the top sheet, and you get back to the one beneath only when the top is done.
chaining: One way of handling collisions: each slot holds a small list, and everything that lands on that slot goes into the list.
class: A blueprint describing what a kind of thing knows about itself and what it can do. You use the blueprint to create individual things.; The architectural plan for a house. The plan is the class; each house actually built from it is an object.
collision: When two different labels produce the same storage slot in a hash table. The table needs a plan for this, or one value would overwrite the other.
compiler: A program that translates code into a form the machine runs directly. Python does not make you run one, which is part of why it is easier to start with.
composition: Building a bigger thing by having one object hold a reference to another. It is the idea underneath linked lists and trees.
conditional: A fork in the road: run these steps only if something is true, otherwise run those steps instead. In Python this is if / elif / else.
DAG: A directed graph with no way of looping back to where you started. Short for directed acyclic graph. Task dependencies form one.
data structure: A particular way of arranging information in a computer’s memory so that certain jobs become fast. Different arrangements make different jobs easy.; How you organise a kitchen. Spices on an open rack makes finding them fast; spices in a random box makes it slow. Same spices, different structure.
database index: A prepared lookup structure a database keeps beside your data so it can find rows without reading every single one of them.
depth-first search: Exploring a graph by going as deep as possible down one path before backing up and trying another.
deque: A queue you can add to and take from at both ends. Pronounced “deck”; short for double-ended queue.
dictionary: Python’s built-in lookup table. Instead of positions, you store things under labels of your own choosing, and fetch them back by that label.; A real dictionary: you do not scan every page, you jump straight to the word you want.
directed: A connection that only goes one way. “A follows B” is directed; “A and B are friends” is not.
divide and conquer: Splitting a problem into smaller versions of itself, solving each one, then combining the results.
dynamic array: An array that grows on demand. When it runs out of room it quietly makes a bigger one and copies everything across. A Python list is one of these.
dynamic programming: Solving a big problem by solving small overlapping pieces once each and reusing those answers, instead of recomputing the same piece thousands of times.
edge: One connection between two vertices in a graph — a road, a friendship, a dependency.
element: A single item stored inside a list, array or similar collection.
exception: The computer’s way of saying “I cannot continue”: an error raised mid-run that stops the program unless you have said what to do about it.
function: A named block of steps you can run whenever you want, instead of writing those steps out again every time you need them.; A button on a microwave. “Popcorn” runs a fixed sequence you never have to think about again.
graph: Things, and the connections between them. Unlike a tree, connections can go in any direction and loop back on themselves.; A map of cities joined by roads, or people joined by friendships.
greedy algorithm: An approach that always takes whatever looks best right now and never reconsiders. Fast, and correct only for certain problems.
hash function: A calculation that turns any label into a number, always giving the same number for the same label. That number decides where the value gets stored.
hash table: The machinery underneath a dictionary: it uses a hash function to work out where to put each item, so finding it again later is instant instead of a search.
heap: A tree arranged so the smallest (or largest) item is always at the top and cheap to grab. It is not fully sorted — only the top is guaranteed.
immutable: Cannot be changed after it is created. If you want a different value you make a new one, rather than editing the old one.
in-place: Rearranging data where it already sits, rather than building a second copy. Uses far less memory.
index: The position number of an item in a list. In Python, counting starts at 0, so the first item is at index 0 and the third is at index 2.
linked list: A chain of small boxes, where each box holds a value and a reference to the next box. There is no instant jumping — you follow the chain.; A treasure hunt where each clue tells you where to find the next clue.
list: Python’s built-in ordered collection. You can put things in, take things out, and reach any item instantly by its position number.
loop: An instruction to repeat a block of steps — either a fixed number of times, or until some condition stops being true.
memoisation: Remembering the answer to a calculation the first time you work it out, so repeat requests are instant instead of recalculated.; Writing an answer in the margin so you never have to redo the sum.
memory: The computer’s short-term working space, where your program keeps everything it is currently using. Separate from the disk, which keeps things after the program closes.
method: A function that belongs to a class — an action an object can perform on itself.
module: A separate file of code you can pull into another file, so one program can be split across several tidy files.
node: One box in a chain or a tree — it holds a value plus references to whichever nodes come next.
O(1): Work that takes the same time no matter how much data there is. Looking up item number 500 in a list is O(1) — the size of the list does not matter.
O(log n): Work that grows very slowly, because each step throws away half of what is left. Doubling the data adds only one extra step.; Guessing a number between 1 and 1,000 by always halving the range. A thousand possibilities takes about ten guesses; a million takes about twenty.
O(n): Work that grows in step with the amount of data. Twice the data means roughly twice the time. Reading every name on a list is O(n).
O(n²): Work that grows brutally: ten times the data means roughly a hundred times the time. Usually a sign you have a loop running inside another loop.
object: One actual thing made from a class, holding its own information. Two objects from the same class have the same abilities but different contents.
pointer: A value holding the location of something in memory rather than the thing itself. Python hides these from you, but they are what references are underneath.
prefix sum: A prepared table of running totals, so that afterwards you can answer “what do items 5 to 900 add up to?” with one subtraction instead of hundreds of additions.
priority queue: A queue where the most important item comes out next, regardless of when it went in.; A hospital waiting room, where the most urgent patient is seen first.
queue: A collection where you add at the back and take from the front. The first thing in is the first thing out.; An actual queue at a shop.
recursion: A function that calls itself on a smaller version of the same problem, with a stopping rule so it does not go on forever.; Standing between two mirrors. Each reflection contains a slightly smaller copy of the same scene.
reference: A pointer to where something lives, rather than a copy of the thing itself. Two names can refer to one object, and changing it through either name changes it for both.; A contact in your phone. You hold the number, not the person; several contacts can point at the same person.
return: What a function hands back to whoever called it. This is different from printing: printing shows a value to a human, returning gives it to the rest of your program to use.
self: Inside a class, the word Python uses to mean “this particular object”. It is how a method reaches the information belonging to the one object it was called on.
set: A collection that refuses duplicates and does not care about order. Useful when you only need to know whether something is present.
sliding window: Looking at a fixed-size stretch of a list, then sliding it along one step at a time instead of re-examining the whole stretch each time.
sorting: Rearranging items into order — smallest to largest, A to Z, oldest to newest.
stable sort: A sort that keeps equal items in the order they were already in. It matters when you sort by one thing after having sorted by another.
stack: A collection where you only ever add to the top and take from the top. The last thing in is the first thing out.; A pile of plates. You take the one you put down most recently.
stack frame: One entry on the call stack, holding one function call’s own variables. Deep recursion means many frames, and frames take up real memory.
stack trace: The report printed when a program crashes, listing which line failed and which calls led there. Read it from the bottom upwards.
standard library: The code that ships with Python itself — thoroughly tested tools you can use without installing anything.
syntax: The grammar rules of a programming language — where the brackets, colons and indentation have to go. Getting it wrong stops the program running at all.
traversal: Visiting every node in a tree or graph exactly once, in some deliberate order.
tree: Information arranged in a branching hierarchy: one thing at the top, each thing below belonging to exactly one thing above, and no loops back upwards.; Folders on your computer. One folder contains others, which contain others.
trie: A tree for words, where each step down spells one more letter, so every path from the top spells a prefix. Pronounced “try”.; The autocomplete on your phone keyboard narrowing its suggestions as you type each letter.
tuple: Like a list, but frozen — once you have made it, you cannot change what is inside.
two pointers: Keeping track of two positions in a list at once and moving them deliberately, which often replaces a slow loop-inside-a-loop with a single fast pass.
variable: A name you attach to a piece of information so you can refer to it later, like writing “price” on a sticky note stuck to a number.
vertex: One of the things in a graph — a city on the map, a person in the network. More than one are called vertices.
weighted: A connection carrying a number — a distance, a cost, a travel time — so some routes are more expensive than others.