What is computational complexity?

What it is: a measure of how much effort an algorithm needs — how much it costs to run.

Why we use it: many algorithms can solve the same problem. We want to pick the cheapest one.

The two costs:

• Time — how long it takes. This is the most significant one for us.
• Space — how much memory it uses.

Why not just time it in seconds?

Because real time is unfair. It depends on things that have nothing to do with the algorithm:

• The machine — the same program runs faster on a home PC than on the lab PCs.
• The language — a compiled C++ program is much faster than the same program in Basic.

So to compare in real time, everything would have to run on the same machine. Instead, we use logical units: we describe the relationship between

• n = the size of the data (the file), and
• t = the time taken to process it.

Time / size relationships

Linear: t = c·n

Time grows at the same rate as the data. If the data doubles, the time doubles too.

Tiny example: if 10 items take 10 steps, then 20 items take 20 steps.

Logarithmic: t = log₂ n

Doubling the data adds just one time unit. This is very fast.

Tiny example: log₂ 8 = 3 steps. Double the data to 16 → log₂ 16 = 4 steps. Twice the data, only +1 step.

Asymptotic complexity

What it is: real cost formulas are messy. We only care what happens when n gets large. So we drop every term that stops mattering. What is left is the asymptotic complexity.

The slide example:

F(n) = n² + 100n + log₁₀n + 1000

Look at the pattern: for small n the constant 1000 is the biggest part (90.8%!). But as n grows, n² takes over — at n = 100,000 it is 99.9% of the whole value. So for large n, only n² matters:

F(n) ≈ n²  →  O(n²)

Big O, Big Ω, Big Θ

Three symbols for describing growth. They simplify complexity equations:

• Big O (Big Oh) — an upper bound. "It grows no faster than this." The one we use most.
• Big Ω (Big Omega) — a lower bound. "It grows at least this fast."
• Big Θ (Big Theta) — a tight bound. Upper and lower at the same time: "it grows exactly like this."

How to simplify

• Drop constant factors: O(2n) → O(n). O(½n²) → O(n²).
• Drop smaller terms: O(n² + 100n + 1000) → O(n²).

Example code — spot the complexity

Each block below is a growth rate you must recognize on sight.

Arrays — the simplest structure

What it is: a collection of elements sitting next to each other in memory. Each element has an index (a number key).

Why it's fast: finding an element is just math. If an int array starts at memory address 1000, and each int is 4 bytes:

address of a[i] = 1000 + 4 · i

Tiny example: a[5] lives at 1000 + 4·5 = 1020. One calculation → O(1) access. No searching.

Three ways to index

• Zero-based — first element is a[0]. This is C++.
• One-based — first element is a[1].
• N-based — start anywhere, even letters: Country[th] = "Thailand".

Dimensions & memory order

A single dimension array has 1 index: a[4]. A multidimensional array has more: a[2][3].

A 2D array is still stored in one flat row of memory. There are two orders:

Static vs dynamic arrays

• Static: memory given at COMPILATION TIME. Size is fixed forever. int a[10];
• Dynamic: memory given at RUN TIME. Size can be chosen while running. int* a = new int[10];

Dynamic memory must be given back: delete [] a;

A jagged array is an array of arrays where each row has a different size:

Array performance, benefits, limits

Benefits: good locality of reference (temporal + spatial → data caching works well), compact (low memory), and random access.

The limit: elements are locked in place, evenly spaced. Inserting inside means shifting other data. The fix for that → a linked structure.

Singly linked lists

What it is: a chain of nodes. Each node holds some data (info) and a pointer to the next node. A pointer head points to the first node. The last node points to NULL (0) to say "I am the end."

Why: no fixed size, and inserting/removing does not shift anything — we just re-aim pointers.

Building a small list by hand:

Insertion: head_insert & tail_insert

Two basic choices, also called push_front() and push_back().

head_insert — new node becomes the first node

1. Make the new node: Node* tmp = new Node(x);
2. Point it at the old first node: tmp->next = head;
3. Move head to it: head = tmp;

tail_insert — new node becomes the last node

Keep a second pointer tail aimed at the last node. Then: make the node, set tail->next = tmp;, move tail = tmp;. Same idea as head_insert, just at the other end.

Inserting in the middle: walk to the spot first, then re-aim two pointers. Compare with an array: no shifting needed!

Deletion — where the traps live

Delete from the head

Trap: if you run delete head; first, you lose your only way into the list! The safe 3 steps:

1. Node* tmp = head; — remember the old first node.
2. head = head->next; — move head to the 2nd node.
3. delete tmp; — now it is safe to free the old node.

Delete from the tail

Problem: the tail's predecessor (the node before it) must become the new tail, but a singly linked list has no backwards pointers. So we must walk from the start to find the second-to-last node:

Always check the special cases

• Empty list — deleting from it would crash. Test isEmpty() first.
• One-node list — after deleting, both head and tail must become NULL.

Efficiency

• Best case: deleteHead() = O(1).
• Worst case: deleteTail() = O(n) (walk the whole list).
• Average: between 1 and n → n/2 → O(n). Search (isInList()) is the same: best O(1), worst and average O(n).

Doubly linked lists

What: each node has two pointers — next and prev. You can walk both directions.

Why: the whole point is the tail. tail = tail->prev; finds the predecessor instantly, so deleting the tail becomes O(1) — no walking.

The cost: insertion and deletion must fix more pointers (easy to get wrong), and each node needs extra memory. Same special cases: empty list, one-node list.

Circular linked lists & circular arrays

Circular linked list: the last node points back to the first — no NULL, no real start or end. Just one current pointer into the ring.

Why: perfect for taking fair turns:

• Processors sharing one resource — each gets its turn as current moves around.
• A multiplayer board game (poker) — current tracks whose turn it is.

Circular array (ring buffer): the same turn-taking idea with an array. It is stored as a normal array plus two variables: the index of the first and last element. When we reach the end of the array, we wrap around and reuse the free cells at the start.

Arrays vs linked lists — who wins?

Both store linear data. Neither is "better" — it depends on the job.

Sparse tables — the CMU grades story

What it is: a table that is mostly empty. Storing it as a full 2D array wastes huge space.

The slide example: store a grade for every CMU student in every course.

• ~25,000 students × ~1,000 courses × 1 byte per grade = 25,000,000 bytes.
• But students take about 7 courses each: 25,000 × 7 = 175,000 bytes of real data.
• 175,000 ÷ 25,000,000 = 0.007 → 99.3% of the table is empty!

Fix 1: two arrays

ClassesTaken (classes for each student) and StudentsInClasses (students in each class). Assuming max 8 classes each and max 200 students per class, 3 bytes per entry: 600,000 + 600,000 = 1,200,000 bytes — under 5% of the original.

But: what if a student takes more than 8 classes? Or a class has more than 200 students? Fixed limits are guesses.

Fix 2: linked lists

Use two arrays of linked lists (one list per student, one per class). No limits to guess, and even more space saved.

Example code — a working singly linked list

Stacks — LIFO

What it is: a linear structure you can only touch at one end — the top. New data goes on the top. Data also comes off the top.

Picture it: a stack of trays in the canteen. You take the tray that was put there last. That rule is called LIFO — Last In, First Out.

The 5 key operations

• clear() — empty the stack.
• isEmpty() — is it empty?
• push(el) — put el on the top.
• pop() — take the top element off (and give it back).
• topEl() — look at the top element without removing it.

Stack use: matching delimiters

A compiler must check that ( ), [ ], { }, /* */ are matched correctly. The rule:

• See an opener → push it.
• See a closer → pop; it must match. (Pop from empty = error.)
• At the end, the stack must be empty.

Case A (from the slide) — success: while(m<(n[8] + o)) {p=7; /*initialise p*/ r=6;}

Case B — error: a = b + ( c − d ) * ( e − f )) — the final ) arrives when the stack is already empty. Nothing to pop → error.

Implementing a stack: vector or linked list?

Both work. Here is the vector version from the slides:

The linked-list version is the same idea, but stores elements in a list<T> instead of a vector<T>.

Comparison (exam favourite)

• The linked list matches the stack more closely — no unused "capacity". In the vector version, capacity can be larger than the size.
• Push and pop are O(1) in both.
• But: pushing to a full vector forces it to allocate new memory and copy everything across — O(n) for that one push.

The STL stack (Standard Template Library)

Key members: empty(), pop(), push(el), size(), top().

Careful: STL pop() is void — it removes the top element but does not return it. Read it with top() first.

Queues — FIFO

What it is: a waiting line that uses both ends: data is added at one end and taken from the other. Like a queue in a bank. The rule is FIFO — First In, First Out.

The 5 key operations

• clear() — empty the queue.
• isEmpty() — is it empty?
• enqueue(el) — add el to the end of the line.
• dequeue() — take the first element out.
• firstEl() — look at the first element without removing it.

Why: simulating real queues — e.g. how many bank staff keep service good, or how many toll kiosks to open.

Queue in an array → the circular array

The problem: in a plain array, every dequeue frees a cell at the front — and that space is never used again. The queue slides down the array and runs out of room.

The fix: a circular array. It's really a normal one-dimensional array plus two index variables, first and last. When we hit the end of the array, we wrap around and reuse the free cells at the start. The "circle" is just how we picture it.

The extra work is in enqueue() / dequeue(): check if we are at the last cell, and make sure we never overwrite the first element.

Better queue: the doubly linked list

With a doubly linked list, adding at one end and removing at the other are both O(1) — we hold pointers to both ends and can step from them directly.

With a singly linked list, one of the two ends needs an O(n) walk to reach its neighbour. That's why doubly wins here.

The STL queue's key members: back(), empty(), front(), pop(), push(el), size().

Priority queues

Why: real queues are rarely fair. A police car reaches the toll — it goes first. In a priority queue, elements leave based on their priority and their current position, not just arrival order.

Ways to build one

Heaps — a first look

What it is: a kind of binary tree where:

• every node's value is greater than or equal to the values in its children, and
• the tree is perfectly balanced — the last-level leaves are pushed to the leftmost positions.

As a priority queue: the value = the priority, so the root is always the highest priority.

Enqueue (add)

1. Add the new element at the bottom of the heap, as a leaf.
2. Let it climb up: swap it with its parent while it has higher priority.

Dequeue (remove the best)

1. Remove the root — the highest priority.
2. Move the last node into the root's place.
3. Let it sink down: swap with its bigger child until it fits.

Each move follows one path up or down the tree — and the tree is short (that's the balance). Compare that with the O(n) linked-list searches above. Much more on heaps in Week 4.

Trees — the words you must know

Why trees: lists are one-dimensional. Much real data is a hierarchy: family trees, the grammar of a sentence, the taxonomy of organisms. Trees store hierarchies.

Picture an upside-down tree: root at the top, branches going down, leaves at the bottom. A tree is nodes connected by arcs.

• Root — the only node with no parent.
• Leaf — a node with no children.
• Path — for each node there is a unique path from the root to it. The length of the path = the number of arcs in it.
• Level of a node = path length + 1 (the root is level 1).
• Height of the tree = the highest path length (counted in arcs).

A tree can be empty. A tree can be one single node — then that node is both the root and a leaf.

Binary trees & Binary Search Trees

Binary tree: every node has at most 2 children (0, 1, or 2). Think of how If–Else splits into two paths.

Complete binary tree: every non-terminal (internal) node has 2 branches. Useful fact: if every nonterminal node has exactly 2 nonempty children, then

m = k + 1  (leaves m are one more than nonterminal nodes k)

Binary Search Tree (BST), also called an ordered binary tree, adds one rule. For each node holding value v:

• everything in its left subtree is less than v, and
• everything in its right subtree is greater than v.

Like the game "guess my number between 1 and 10" — each guess cuts the field in half.

A Binary Search Tree. Left of 5: all smaller. Right of 5: all bigger.

Implementing a binary tree

Why not an array? Deleting a node leaves empty cells, and inserting can push related nodes far apart. Inconvenient — so we use nodes and pointers.

The two-class design: BSTNode (one node: a key + left/right pointers) and BST (owns the root, does the work). BSTNode's members are public so the BST class can reach them.

Searching a BST

How it works: start at the root. Searching for el:

• el equals the node → found, stop.
• el is lower → follow the left pointer.
• el is higher → follow the right pointer.
• You reach NULL → el is not in the tree.

How fast?

• Worst case: O(n) — the tree is shaped like a linked list (every node one child).
• Average case: IPL ÷ n. IPL = Internal Path Length = the sum of the path lengths of all nodes. So the average depends on the tree's shape.
• Best shape: a complete tree. 10,000 nodes: worst shape needs up to 10,000 tests — balanced needs only 14, because the height is lg(10,001) ≈ 13.3 → 14.

Tree traversal — visiting every node once

What: visit each node exactly once. With n nodes there are n! possible orders — only a few are practical. Two families:

1 · Breadth-first — level by level

Top-down, left-to-right (or any of the 4 direction combos). Implemented with a queue: enqueue the root; then repeat: dequeue a node, visit it, enqueue its children.

2 · Depth-first — dive deep, then come back

Built from three moves: V = Visit the node, L = traverse the Left subtree, R = traverse the Right subtree.

(VRL, RVL, RLV also exist — the mirror versions.) In-order on a BST gives the values in sorted order — that's how you turn a BST into a sorted array.

These functions call themselves twice — this is called double recursion.

Traversal without recursion

Recursion quietly uses the runtime stack. Alternatives:

Iterative pre-order — bring your own stack

Push right before left, so the left child pops out first. Is it better? No — no double recursion, but it needs its own stack and up to 4 calls per loop. The real worry is space, not time (all traversals are O(n) time).

Threaded trees — hide the stack inside the tree

Add extra pointers (threads) to each node pointing to its predecessor / successor in the traversal. Either keep 4 pointers per node, or overload left/right to sometimes mean predecessor/successor — but then an extra data member must say which meaning is in use.

Morris's algorithm — reshape instead of remembering

Transform the tree while walking so no stack is needed: a tree with no left children is trivial to traverse (just go right). So LVR becomes VR.

Moved nodes keep their left pointers, so the original shape is restored. Time still depends on the loops (about 5–10% saving in tests on 5,000 random trees) — the clear win is space.

Insertion & Deletion

Insertion — find a dead end

Follow the search rule: bigger → right, smaller → left. When you hit an empty child spot, put the new node there. Simple — but over time this can make the tree very unbalanced.

Deletion — three cases, easy to hard

1. A leaf (no children): just delete it. Its parent points to NULL.
2. One child: delete it. The parent adopts the grandchild (points to the deleted node's child).
3. Two children: now it's interesting. Two strategies: merging or copying.

Deletion by Merging

Cutting out the node leaves 2 subtrees. Every value in the left subtree is lower than every value in the right subtree. So:

• The root of the left subtree replaces the deleted node.
• The rightmost node of the left subtree becomes the parent of the right subtree.

The tree may gain height (like here) or lose it — merging can produce a very unbalanced tree. Not inefficient, but not perfect.

Deletion by Copying

Key insight: the rightmost node of the left subtree is the deleted node's immediate predecessor (and the leftmost node of the right subtree is its successor). So:

• Copy the predecessor's (or successor's) value into the deleted node's spot.
• Then delete that node instead — it's always an easy case (0 or 1 child).

Height does not grow, but always using the predecessor makes the left side bushy — so we can alternate between predecessor and successor.

Balancing a tree

Why bother: 10,000 nodes. Linked-list shape → up to 10,000 tests to find something. Balanced → 14 tests. Same data!

Method 1: rebuild from a sorted array

Put all the data in a sorted array (an in-order traversal gives you that). Then: the middle element becomes the root; the middle of the left half becomes one child, the middle of the right half the other; recurse.

Weakness: needs extra space for the array, and all values must be in it first.

Rotation — the tool behind everything else

A child rotates around its parent (right rotation lifts the left child; left rotation lifts the right child). One thing to burn into memory:

🔑 The middle subtree switches parents.

When child Ch rotates up around parent Par, the subtree between them (Ch's inner child) lets go of Ch and becomes Par's child. Nothing else changes.

Method 2: the DSW algorithm (Day, Stout & Warren)

Devised by Day, improved by Stout and Warren. Two phases, built entirely from rotations:

1. Stretch: turn the tree into a backbone — a linked-list-like tree leaning right. (While a node has a left child, rotate that child up around it.)
2. Balance: rotate every other node around its parent, going down the right branch. Repeat until the tree is perfectly balanced.

DSW rebalances the whole tree in O(n). Good when you only balance once in a while (the cost is amortised) — e.g. after many insertions and deletions.

AVL trees — stay balanced as you go

Named after Adel'son-Vel'ski and Landis. Instead of rebalancing the whole tree now and then (DSW), an AVL tree checks balance on every insertion or deletion and fixes problems locally with rotations.

Every node has a balance factor:

Balance = Height(left subtree) − Height(right subtree)

It must stay at +1, 0, or −1. (Height of an empty subtree counts as −1.) If an insert pushes some node's balance to +2 or −2, we rotate. An AVL tree may not look as perfectly even as a DSW result — that's fine, only the balance factors matter.

The 4 out-of-balance situations → 4 rotations

Name the case by where the new key landed, relative to the unbalanced node:

LL — insert 2 (slide example)

RR — insert 8 (slide example)

LR — insert 3 (slide example, double rotation)

RL — insert 7 (slide example, double rotation)

The "further issue" — imbalance higher up

Insert 9 into the tree above: every node on the way stays legal except 5, higher up, which hits −2. Fix it at that node: 9 sits right-right relative to 5 → RR-style rotation (7 rotates up around 5).

Deletion can also unbalance an AVL tree — also fixed by rotations, but it's more time-consuming: every node between the deleted one and the root must be checked (and possibly rotated).

Self-adjusting trees & splay trees

The idea: balancing assumes every node is equally popular. But some nodes are searched much more often. If the popular ones sit near the top, searching gets faster — even in a tree that isn't perfectly balanced.

Simple strategies: single rotation (rotate the accessed node around its parent) or move to root.

Splay trees

A special self-organizing BST: every access reorganizes the tree so recently used elements are easy to reach. Insertion, deletion and search all run in O(log n) amortized time. Every operation ends with splaying — moving the accessed node up. Three cases:

1. Parent is the root: rotate the node around its parent. Done.
2. Homogeneous (node and parent are both left children, or both right children): rotate the parent around the grandparent first, then the node around the parent.
3. Heterogeneous (one left, one right): rotate the node around its parent first, then around the grandparent.

The verdict (exam-worthy): in theory, self-organizing trees compete well. In experiments, AVL almost always wins — and sometimes even plain BSTs do. Lesson: complexity analysis and amortized analysis aren't always the full story.

Heaps & Heapsort

(Max) heap: a binary tree where each node ≥ its children, perfectly balanced, last-level leaves leftmost. A min heap is the reverse — smallest on top.

As a priority queue (from Week 3): enqueue = add at the bottom, climb up. Dequeue = take the root, move the last node up top, let it sink down. Each is one short path — compare that with O(n) list searches.

Heapsort

Selection sort scans the whole remaining data to find the max each round — O(n²). A heap hands you the max for free (the root). So:

1. Turn the data into a heap.
2. Pop the root (the biggest) — move it to its final position.
3. Fix the heap with the remaining nodes. Repeat.

If the data lives in an array, no second array is needed — sort in place by swapping positions.

Expression trees & Polish notation

What is 2 − 3 * 4 + 5? It depends how you group it! Each grouping is a different expression tree (operators inside, numbers at the leaves):

Now traverse the correct (−5) tree in the three depth-first orders:

Notice: the in-order reading is the same for all three trees — that's exactly why infix needs parentheses, and prefix/postfix don't.

Why binary trees stop working

Last week we assumed everything was in RAM. Now suppose the data is too big and lives on a hard disk. Reaching a piece of disk memory costs:

seek time + rotation time + transfer time

Seek time is the killer. It depends on the disk head physically moving to the right position — mechanical, not electronic.

• Seek time is measured in milliseconds.
• CPU work is measured in microseconds — at least 1,000× faster.

A binary tree is the worst possible shape here: each node holds one key, so descending 5 levels can mean 5 separate disk seeks. It was spread across blocks with no thought for how the disk reads.

Multiway trees — fatter nodes, fewer levels

A multiway tree differs from a binary tree in a few key ways:

• Each node has m children.
• Each node has m−1 keys.
• The keys are in ascending order.
• The keys in the first i children are smaller than the i-th key.
• The keys in the last m−i children are larger than the i-th key.

A multiway tree. Count them: a node with k keys always has k+1 pointers.

This one still suffers from malaise — it is unbalanced, so finding 32 takes longer than finding 21. Fat nodes alone are not enough; we also need every leaf on the same level. That is what a B-tree adds.

B-Trees — one node = one disk block

The idea in one line: make each node exactly the size of a disk block, so one seek brings back as many keys as possible.

How many keys fit in a node depends on the size of each key and the size of the block, and block size depends on the system.

A B-Tree of order m has these properties:

• The root has at least 2 subtrees, unless it is a leaf.
• Each nonroot, nonleaf node holds k−1 keys and k pointers, where ⌈m/2⌉ ≤ k ≤ m.
• Each leaf holds k−1 keys, where ⌈m/2⌉ ≤ k ≤ m.
• All leaves are on the same level.

Nice consequence: the root — and maybe the whole first level — can be kept in RAM, so a search of a big tree may cost only one or two real disk accesses.

Implementing and searching

The node carries its keys and pointers inline, plus a count of how many keys are actually in use:

Searching is just a binary-tree search with a wider fan-out. Start at the root and pick the branch whose range contains the search value:

Within a node you scan the keys in RAM, which is free. Following a pointer is what costs a seek — so the wider the node, the cheaper the search.

Inserting — the tree grows upward

The challenge: in a B-tree all leaves must be on the same level. Not even a balanced binary tree demands that.

So the direction of construction flips. Binary trees are built top down — the root is placed and nodes divide around it. A B-tree is built bottom up — leaves are positioned and rearranged, and the root is decided last.

The algorithm:

• Search the tree to find the leaf the key belongs in.
• If there is room (fewer than m−1 keys already), just insert it. Done.
• Otherwise the node must split. Choose the median: lower keys form the left node, higher keys form the right node.
• The median moves up to the parent — which may itself now be full, so it may split too.
• Repeat upward until something has room, or the root is reached.

Worked example — insert 33, order 5

Order 5 means at most 4 keys per node. Watch the highlighted node.

1 — the target leaf already holds 4 keys. It is full.

2 — inserting 33 gives it 5 keys. Overflow.

3 — split at the median 32. Left keeps 25 30, right takes 33 35, and 32 moves up into the parent. The parent had room, so it stops here.

When the root itself is full

This is the only case where a B-tree gains height.

A full root receives a promoted median and overflows.

It splits in two and a new root is created above them. The tree is one level taller — and every leaf is still on the same level.

Deleting

Deletion asks two questions first:

• Is the key in a leaf? If so, will the leaf still be at least half full afterwards?
• Is it in an internal node? Then which value becomes the new separator?

Leaf nodes can simply be deleted, which may leave the leaf with too few keys. Then the tree must be rebalanced: pick a sibling leaf and redistribute the keys. If a neighbour has enough to share, the median becomes the new separator key and the rest are shared out. If that leaves the parent short of keys, the fix iterates upward toward the root.

Internal nodes cannot just be removed — they separate two subtrees. Promote one of:

• the largest value in the left subtree, or
• the smallest value in the right subtree.

Either choice reduces the problem to deleting from a leaf or from another internal node — both of which we have now defined. Same trick as deleting from a BST.

B*-Trees — delay the split

Every node is a block, and every block costs a seek. B*-Trees reduce accesses further by keeping nodes fuller:

• A B-tree must be at least half full.
• A B*-Tree must be two-thirds full.

How it achieves that: it delays splitting by splitting 2 nodes into 3, rather than 1 node into 2.

• Overflow first. If a leaf fills up but its sibling has room, the surplus overflows into the sibling instead of splitting.
• Split only when both are full. Then the two full nodes become three, each about two-thirds full.

A B**-Tree pushes the same idea again: required to be 75% full.

B+Trees — all data in the leaves

The problem being solved: in-order traversal. On a binary tree, in-order gives you the values in ascending order cheaply. On a B-tree it is awkward — leaves can be read a block at a time, but internal nodes give you only one value per visit, and you keep bouncing between levels.

The fix: in a B+Tree the internal nodes are pure index — signposts only.

• Values stored in index nodes are repeated in the leaves.
• All data lives in the leaves; indexes only point to the right leaf.
• Leaves are chained with forward pointers, so an in-order traversal reads leaves straight through and never touches an internal node.

A B+Tree. The index keys 20 and 30 reappear in the leaves — that is the giveaway.

Insert: when a leaf splits, the promoted value becomes both a value in the leaf and an index in the parent.
Delete: removing a value from a leaf does not require removing the matching index — it is still a perfectly good signpost. If a leaf gets too small it merges with a sibling and the indexes are updated.

Prefix B+Trees and Bit Trees — shrink the index

That last point is the doorway. If an index key does not have to be a stored value, it only has to separate them. So store the shortest thing that still separates.

Prefix B+Tree: the index holds only a prefix of the key — BF instead of BF90, like the guide word at the top of a dictionary page.

• Shorter prefix → more keys per index node.
• More keys → more children per node.
• More children → fewer levels → fewer seeks.

If every key in a region starts AB12XY…, storing "AB" at every level between the leaves and the root is pure waste. Keep only the distinguishing part.

Bit Tree: take it to the extreme. Store the D-bit — the single distinction bit, the first bit position where two values differ:

Especially valuable when the tree stores complicated objects: you never store the object in the index, only enough to steer the search to the right leaf.

Tries

Only a portion of the key is ever needed to search. But finding the right prefix is awkward, and maintaining prefixes is complicated.

A tree that navigates using parts of the key itself is called a "trie."

The name comes from retrieval. Instead of comparing whole keys at each node, you consume the key one piece at a time — one character, or one bit — and that piece chooses the branch. The path from the root spells the key.

Exam traps

• Keys vs pointers. A node with k keys has k+1 pointers. Order m means m pointers and m−1 keys — not m keys.
• "Order 5" is the pointer count. So a node holds at most 4 keys and splits on the 5th.
• Half full, not half empty. B-tree ≥ ½ · B*-Tree ≥ ⅔ · B**-Tree ≥ ¾.
• Splitting promotes the median, and the median goes up, not into either half.
• Height only grows at the root. Every other split is absorbed by a parent.
• B+ ≠ B. In a B+Tree every value is in a leaf and index values are repeated. In a plain B-tree a value appears exactly once, wherever it sits.
• Why any of this exists: seek time. If a question asks "why not just use an AVL tree", the answer is milliseconds vs microseconds.

What the worksheet asks (plain words)

Part 1: Start with an empty tree. Do these operations, in order, then draw the tree:

Insert 10, 5, 29, 4, 8, 28, 3, 6, 15 — then — Delete 3, Delete 28

Part 2: From that result, Delete 10 and draw the tree again.

The plan before drawing

• Insert rule: start at the root. Smaller → go left, bigger → go right. Insert at the first empty spot.
• Delete a leaf: just remove it.
• Delete a node with 1 child: the parent adopts the child.
• Delete a node with 2 children: deletion by copying — copy the successor (the leftmost node of the right subtree) into its place, then remove that node. (The method used in our class. Alternatives shown at the bottom.)

Step by step — the nine insertions

The two deletions → Answer to Part 1

Part 2 — Delete 10 (two children!)

10 has two children (5 and 29) → deletion by copying:

1. Find the successor = leftmost node of the right subtree. Go right to 29, then left as far as possible → 15.
2. Copy 15 into 10's place.
3. Delete the old 15 node — it's a leaf, easy. (29 now has no left child.)

Alternative methods (only if asked for them)

Full solution code

This program builds the worksheet tree, does the deletions, and prints the tree in-order after each part (in-order = sorted, an easy way to check yourself).

Practice — fill in the missing lines

Same code, but the exam-critical lines are gone. Type them, then hit Check.

What the worksheet asks (plain words)

You are given an AVL tree. Part 1: insert 18, keep it balanced, redraw. Part 2: then insert 15, then 14 (continuing from Part 1's result), redraw.

The given tree — balance factors shown beside each node (all legal: −1, 0, +1)

The plan before drawing

1. Insert like a normal BST (smaller left, bigger right).
2. Recompute balance factors up the path: Balance = Height(left) − Height(right).
3. If a node hits +2 or −2: find the lowest such node, name the case by where the new key landed relative to it (LL / RR / LR / RL), and rotate. Remember: the middle subtree switches parents.

Part 1 — Insert 18

Path: 18 > 10 → right · 18 > 13 → right · 18 > 17 → right → new right child of 17.

Which case? Relative to 13, the new key went into the Right subtree of the Right child (into 17's right side) → RR → one left rotation: 17 rotates up around 13.

Part 2 — Insert 15, then Insert 14

Insert 15 — no rotation needed

Path: 15 > 10 → right · 15 < 17 → left · 15 > 13 → right → new right child of 13. Check the factors — everyone stays legal:

Insert 14 — RL case!

Path: 14 > 10 → right · 14 < 17 → left · 14 > 13 → right · 14 < 15 → left → new left child of 15.

Which case? Relative to 13: the key went to the Right child (15), then into its Left subtree → RL → double rotation: first rotate 14 right around 15, then rotate 14 left around 13. 14 ends up as the parent of both.

Solution code — rotations you can run

The exam wants drawings, but these little functions ARE the drawings, in code. Note the "middle subtree" line in each rotation.

Practice — fill in the missing lines

What the assignment asks

The graph has 10 vertices (A–J) and 18 weighted edges. A spanning tree of 10 vertices always has 9 edges.

Part 1 — Kruskal's algorithm

1. Sort all edges by weight, smallest first.
2. Take the next edge. If it joins two vertices that are not already connected, add it. If it would close a cycle, skip it.
3. Stop when the tree has |V| − 1 = 9 edges.

Part 2 — Prim's algorithm from A

1. Start with only A in the tree.
2. Look at every edge with one end inside the tree and one end outside. Add the cheapest.
3. Repeat until every vertex is in the tree.

My answer

Kruskal — order of edges added

C–E (1) → C–F (2) → E–J (2) → F–B (3) → F–H (4) → E–G (4) → A–D (4) → A–J (5) → H–I (8)

Prim from A — order of edges added

A–D (4) → A–J (5) → J–E (2) → E–C (1) → C–F (2) → F–B (3) → F–H (4) → E–G (4) → H–I (8)

Handwritten working

Things that lose marks

• Ties. Edges with equal weight can be taken in either order. In Kruskal, C–F and E–J (both 2) can swap, and so can A–D, F–H and E–G (all 4). In Prim, F–H and E–G (both 4) can swap. Any of these orders is correct.
• Kruskal skips, it does not stop. B–C (5) is the first rejected edge: B and C are already joined through F. Keep going down the sorted list until there are 9 edges.
• Prim grows one connected tree. You cannot take C–E (1) first when starting from A, because neither end is in the tree yet. That is the difference from Kruskal, which can build separate pieces and join them later.
• Count the edges. 10 vertices → 9 edges. More means a cycle; fewer means the tree is not finished.

1 · Core graph definitions

2 · Representing a graph as data

A drawn network is easy for a person to read, but the deck stresses that it is not an effective storage format. Three representations are introduced:

3 · Traversal: DFS vs BFS

Graph traversal means visiting every node once. It is harder than tree traversal because a graph can contain a cycle, so the algorithm marks nodes as visited. Graphs may also contain isolated vertices, so an outer loop is needed to find unvisited parts.

Depthfirstsearch()
for all vertices v
    num(v) = 0
edges = null
i = 1
while there is a vertex v with num(v) = 0
    DFS(v)
output edges

DFS(v)
num(v) = i++
for all vertices u adjacent to v
    if num(u) is 0
        attach edge(uv) to edges
        DFS(u)

Breadthfirst()
for all vertices u
    num(u) = 0
edges = null
i = 1
while there is a vertex v such that num(v) == 0
    num(v) = i++
    enqueue(v)
    while queue is not empty
        v = dequeue()
        for all vertices u adjacent to v
            if num(u) is 0
                num(u) = i++
                enqueue(u)
                attach edge(vu) to edges
output edges

4 · Shortest paths

Dijkstra's algorithm — one start vertex

Each edge in a weighted graph has a value. The shortest path is the path with the least total value. Dijkstra starts every current distance at ∞, except the first vertex at 0. It repeatedly selects the unchecked vertex with the smallest current distance and tests whether it gives its neighbours a shorter route.

DijkstraAlgorithm(weighted simple digraph, vertex first)
for all vertices v
    currDist(v) = ∞
currDist(first) = 0
toBeChecked = all vertices
while toBeChecked is not empty
    v = a vertex in toBeChecked with minimal currDist(v)
    remove v from toBeChecked
    for all vertices u adjacent to v and in toBeChecked
        if currDist(u) > currDist(v) + weight(edge(vu))
            currDist(u) = currDist(v) + weight(edge(vu))
            predecessor(u) = v

All-to-all shortest paths — WFI

The Warshall–Floyd–Ingerman algorithm starts from a weight matrix where non-directly-connected nodes have distance ∞, then repeatedly tests whether routing through an intermediate vertex improves a pair's distance.

WFIalgorithm(matrix weight)
for i = 1 to |V|
    for j = 1 to |V|
        for k = 1 to |V|
            if weight[j][k] > weight[j][i] + weight[i][k]
                weight[j][k] = weight[j][i] + weight[i][k]

5 · Cycle detection and Union-Find

Cycle detection

The deck extends DFS: if an adjacent vertex is already visited and the edge is not already one of the traversal edges, a cycle is detected. It notes that digraphs are slightly more complicated.

DFS(v)
num(v) = i++
for all vertices u adjacent to v
    if num(u) is 0
        attach edge(uv) to edges
        DFS(u)
    else if edge(vu) is not in edges
        cycle detected

Union-Find

Union-Find first finds which set an element belongs to, then unions two sets. In this graph context it can be used to determine whether two nodes are connected. The supplied description merges sets into a linked list.

6 · Spanning trees: Kruskal and Prim

A spanning tree keeps all destinations connected while removing unnecessary routes. When edge costs matter, the goal is a minimum spanning tree.

Kruskal(weighted unconnected undirected graph)
tree = null
edges = sequence of all edges of graph sorted by weight
for (i = 1; i ≤ |E| and |tree| < |V|-1; i++)
    if e from edges does not form a cycle with edges in tree
        add e to tree

Kruskal repeatedly tests the smallest available edge and adds it only if it does not create a cycle, stopping when the spanning tree is complete.

Prim's algorithm

Prim reaches a minimum spanning tree a different way: start from one vertex and repeatedly add the cheapest edge that joins a vertex in the tree to a vertex outside it. Kruskal can build separate pieces and join them later; Prim always grows one connected tree.

ASSIGNMENT 4 · KRUSKAL & PRIM STEP BY STEP →

7 · Topological sort and networks

Topological sort

Some digraphs represent tasks that must happen in a particular order. Topological sort orders their vertices by repeatedly locating a minimal vertex, numbering it, and removing it and its edges.

toposort(digraph)
for i = 1 to |V|
    find minimal vertex v
    num(v) = i
    remove v from digraph and all edges

Network

The deck defines a network as a special digraph with one source (no incoming edges), one sink (no outgoing edges), and a capacity on each edge. Examples include water through pumps/pipes and data through a computer network.

8 · Eulerian graphs and the Chinese Postman

The deck states: a graph is Eulerian if every vertex is incident to an even number of edges; a graph contains an Eulerian trail if it has exactly two odd-degree vertices.

Chinese Postman

The goal is to traverse every street at least once and return to the start using as short a walk as possible. If the graph is not Eulerian, repeat edges between odd-degree vertices until there are no odd-degree vertices, choosing short repeats where possible.

9 · Hamiltonian graphs and TSP

A Hamiltonian cycle passes through all vertices of a graph. A Hamiltonian graph has at least one Hamiltonian cycle. The deck states that all complete graphs are Hamiltonian.

Travelling Salesman Problem

The TSP asks for the shortest Hamiltonian cycle: visit every city while choosing the shortest tour.

The deck presents two approximate approaches:

1. Begin with a minimum spanning tree, follow it, and use triangle shortcuts when a node would be visited again. The deck states the TSP solution should be no more than 2 × l, where l is the minimum spanning tree length.
2. Begin at a root, insert its nearest neighbour to make a loop, then repeatedly add the next nearest neighbour by linking it to its two closest neighbours until all nodes are linked.

1 · Agents, percepts and actions

Vacuum Cleaner World

Two locations, A and B, which can be dirty. The agent perceives where it is and whether that square is dirty. Its actions are suck, move left, move right or do nothing.

A simple agent function: "If the current square is dirty, suck. Otherwise move to the other square." Whether that is good depends on how success is measured.

2 · Rationality and performance measures

A rational agent does the right thing, the thing that makes it most successful. So we need a performance measure: an objective test of success set by the designer (not the agent's own opinion, which could be delusional).

What is rational at any moment depends on four things:

1. The performance measure that defines success.
2. The agent's prior knowledge of the environment.
3. The actions the agent can perform.
4. The percept sequence to date.

3 · Task environments

4 · Agent programs

The simplest program is a lookup table from percepts to actions. It works, but it does not scale: a table for chess would need about 10¹⁵⁰ entries. So the table has to be replaced by short code.

5 · Problem-solving agents

1. Goal formulation: identify the goal states, the set of states where the goal is satisfied.
2. Problem formulation: pick the subset of states and actions worth considering (in chess, ignore "knock the board over").
3. Search for a sequence of actions → the sequence is the solution → execute it.

The 16 grid (sliding-tile puzzle)

The search takes the form of a tree traversal. Several actions lead back to a state seen before, which can cause an infinite loop. The 16 grid is NP-hard: no polynomial-time algorithm is known (the slides put it as "no algorithm can solve the problem in polynomial time"), but a proposed solution can be checked very quickly.

6 · Uninformed search

No information about where the goal is. The agent can only generate successors and tell goal from non-goal states. In the diagrams, red nodes are states that repeat an earlier state.

7 · Informed (heuristic) search

Uninformed search is inefficient. If something is known about the environment, a heuristic function can say which direction looks better.

Dijkstra's algorithm is related: it returns the shortest route from the start node to every other node.

8 · Local search and optimisation

Sometimes the route does not matter, only a goal state or the best state found.

1 · Game theory

Game theory is a branch of economics that studies any multi-agent environment where one agent's actions affect another agent, cooperatively or competitively.

The Prisoner's Dilemma

Two suspects are held separately and offered the same deal. Neither knows what the other will choose.

The lecture's "Who stole the final exam?" game has the same shape: your grade for Admit / Accuse / Deny depends on what everyone else chooses.

2 · What counts as a "game"

In AI, games are deterministic, turn-taking, two-player, zero-sum games with perfect information: a deterministic, fully observable environment where two agents alternate moves and the final utilities are equal and opposite (chess: winner +1, loser −1, or 0 for a draw).

Games suit AI because they are easy to represent, the agent has a small number of actions and the results of actions are well defined (unlike football, with imprecise rules and a huge range of actions).

3 · Game trees and minimax

From the definition we can build a game tree. A normal search returns a fixed sequence of actions, but here the opponent also moves, so we need a contingent strategy. The optimal strategy does at least as well as any other against an infallible opponent.

The minimax algorithm assumes the opponent plays optimally and maximises the worst-case outcome.

4 · Alpha-beta pruning

If a player already has a better choice at the parent of node n or anywhere higher up, n will never be reached, so it can be pruned (not searched).

1. Search a1 depth-first: worst case 3.
2. Search a2: the first leaf is 2, already worse than 3. Stop. c2 and c3 are pruned.
3. Search a3: 10 and 11 are not worse than 3, so all three leaves must be examined before the 2 is found.

5 · Imperfect, real-time decisions

The program must decide within a time limit, so the search is cut off at a non-terminal state and that state is scored with a heuristic evaluation function.

Features are weighted by importance, possibly using the probability of success from past experience.

Games with chance

Backgammon mixes skill with dice. We do not know the opponent's possible moves, only their likely ones, so the game tree is expanded to include the probabilities of each dice roll.

6 · Acting under uncertainty

To catch a flight: plan A60 leaves 60 minutes before check-in, B90 leaves 90 minutes before. We can never say "A60 will get us there on time", only "…as long as there is enough fuel, no accident, no breakdown…". B90 raises the degree of belief of arriving on time but adds a long unproductive wait. Both goals matter: getting to the airport and avoiding a long wait.

7 · Probability basics

Joint probability table: Late, Male, AM

P(Male OR Late) = 0.22 + 0.25 + 0.10 + 0.18 + 0.08 + 0.10 = 0.93 (every cell that is male or late).

P(Male AND Late) = 0.22 + 0.10 = 0.32.

Product rule

P(a ∧ b) = P(a | b) · P(b)
P(a ∧ b) = P(b | a) · P(a)

Both forms are true, but one usually makes more sense: "a man being late in the morning given that it is sunny" is sensible; "it being sunny given that a man is late" is not, because lateness does not cause the weather.

Bayes' law

P(b | a) · P(a) = P(a | b) · P(b)

P(b | a) = P(a | b) · P(b) / P(a)

It needs two unconditional probabilities and one conditional probability to give one more conditional probability.

8 · Wumpus World

A 4×4 cave. The Wumpus eats anyone who enters its room; pits trap anyone who enters; there is one heap of gold. The agent turns left or right by 90° or walks forward, and can shoot one arrow in a straight line.

The full map (the agent cannot see this). Rooms are written (column, row) from the bottom-left start (1,1).

How the agent reasons

1. At (1,1): no stench, no breeze → (1,2) and (2,1) are OK.
2. Move to (2,1): breeze → a pit is in (2,2) or (3,1). Mark both ?P and go back.
3. Move to (1,2): stench but no breeze. No breeze → (2,2) has no pit, so the pit is in (3,1). There was no stench at (2,1), so the Wumpus is not in (2,2) → it is in (1,3). (2,2) is OK.
4. Move to (2,2): glitter → the gold is in (2,3) or (3,2).

Question: breeze in both (1,2) and (2,1)

Now logic alone cannot say where the pit is. The unknown neighbours are (1,3), (2,2) and (3,1). A breeze in (1,2) needs a pit in (1,3) or (2,2); a breeze in (2,1) needs a pit in (2,2) or (3,1). A single pit in (2,2) explains both breezes, so it is the most likely.

1 · Encoding and its assumptions

The same value can be written many ways. The number 128 is 128, ๑๒๘, 80 (hex), 10000000 (binary), CXXVIII, ρκη, or 128 tally marks. Storing M/F instead of Male/Female is already compression.

• There are n different symbols available for the code. Morse code: n = 3 (technically 5). Binary: n = 2.
• Each message symbol mi has a probability of occurrence P(mi), and all the probabilities add up to 1.
• Infrequent symbols get a long codeword; short codewords are kept for frequent symbols.

2 · Coding objectives and the prefix property

1. Each codeword corresponds to exactly one symbol.
2. Decoding should not require any look-ahead. This is the prefix property: no codeword is the beginning of another codeword.

Code optimisation

• A more likely symbol must not have a longer code than a less likely one: if P(mi) ≤ P(mj) then L(mi) ≥ L(mj).
• There should be no unused short codes, either as codes or as prefixes of longer codes. 01, 000, 001, 100, 101 is not ideal because 11 is never used.

3 · Huffman coding

Huffman coding chooses a bit string for each symbol so that the result is a prefix-free code, with the most common symbols using the fewest bits.

1. Start from the frequencies of the symbols. Every symbol is a leaf.
2. Repeatedly join the two lowest-frequency nodes under a new parent whose value is their sum.
3. Stop when one node is left. The root equals the total (1.0 as a probability, 120 here).
4. Read each code from the root: 0 for a left branch, 1 for a right branch.

One valid order of joins: F+I = 10 · C+10 = 15 · A+15 = 25 · B+D = 30 · G+E = 35 · 25+30 = 55 · H+35 = 65 · 55+65 = 120. Ties can be broken differently, so several trees are possible.

Decoding practice

Read bits left to right; as soon as the bits match a code, output that symbol and start again. No look-ahead is needed, so the code meets the prefix requirement.

4 · Adaptive Huffman

Huffman coding (1950s) assumes the frequency of each symbol is known in advance. Frequencies could come from a large corpus such as the BNC, but that tree may not suit every text: a technical computing paper has far more non-alphabet symbols than War and Peace.

Adaptive Huffman rebuilds the tree as the data is read in:

• At the start every symbol is unused and stored together in one leaf with value 0.
• When a symbol is used it is split out of that leaf and its count increases, so it moves up the tree.
• As counts grow, a node is compared with its siblings and swapped (transposed) if necessary to keep the tree ordered.
• Sibling comparison is easy when the tree is also stored as a doubly linked list.

5 · Run-length encoding

Replace a run of repeated symbols with a count and the symbol. The word cabbage has a repeated b, so the code can say "2 b's". The Thai repeat mark ๆ works the same way.

AAAABBBCCD   →   4A3B2C1D

The paper at a glance

Question 1 · The graph33 marks

Every part of Question 1 uses this graph: 11 vertices (A–K) and 21 weighted edges.

Sorting the edges like this before you start saves time in parts c and d.

Question 2 · The AVL tree10 marks

Balance factor = height(left) − height(right), written beside each node. All are −1, 0 or +1, so the tree is a valid AVL tree.

Question 3 · Connect 417 marks

Connect 4: two players take turns dropping a disc into one of 7 columns of a 6-row grid. The first to line up four discs wins. On each turn there are at most 7 possible moves.

Short forms ↔ long forms

The growth ladder & key formulas

Slowest-growing (best) → fastest-growing (worst)

Formulas to write without thinking

• Array address: address(a[i]) = base + elementSize · i — e.g. base 1000, 4-byte ints: a[i] at 1000 + 4i.
• Complete binary tree: m = k + 1 (leaves = nonterminal nodes + 1).
• Path length = arcs from root · Level = path length + 1 · Height = longest path length. Empty subtree height = −1.
• Balance = Height(left) − Height(right) ∈ {−1, 0, +1}; at ±2 → rotate at the lowest bad node.
• Average BST search = IPL ÷ n. Balanced tree of 10,000 nodes: height = lg(10,001) ≈ 13.3 → 14 tests.
• Sparse table (CMU): 25,000 × 1,000 = 25 MB table, only 0.7% used → 99.3% empty; two arrays < 5%; linked lists even less.

Arrays & linked lists — every operation, every cost

Array

Singly linked list

Doubly linked list

Stacks, queues & priority queues — every function

Stack (LIFO)

Queue (FIFO)

Priority queue — 4 ways to build it

Trees — every operation, every cost

🔑 One line to rule all rotations: the middle subtree switches parents.

Graphs — Week 7 quick reference

Agents & search — Week 10 quick reference

Games & probability — Week 12 quick reference

Compression — Week 13 quick reference