1
Cost a sequence, and label the cost
Run an operation sequence on a named structure and say whether its cost is worst-case, amortised or expected — three different promises that a single measurement cannot tell apart.
Course · Algorithms
Data Structures
Discrete Mathematics analysed algorithms and never built a structure to run one on. This course builds eight, and costs each by executing an operation sequence rather than by quoting a class — because the interesting facts here are all about the difference between a worst case, an amortised bound and an expectation, and those three are indistinguishable from a single fast run.
heap: parent ≤ children array layout, children of i at 2i, 2i + 1
Σ ⌈n/2ʰ⁺¹⌉·h < 2n build-heap is linear, n inserts are not
chaining: Θ(1 + α) expected, Θ(n) worst — no hash function removes it
AVL: |h_L − h_R| ≤ 1 everywhere ⟹ h ≤ 1.44 log₂ n, by Fibonacci
What this course is about
- Subject
- Algorithms
- Lessons
- 14
- Format
- Interactive
Overview
What you will be able to do
By the end you can cost an operation sequence on any of eight structures, say for each cost whether it is worst-case, amortised or expected, and choose a structure from a workload while naming what the choice cannot do.
2
Operate each structure by hand
Heap insert and extract, hash insert with chaining and with probing including deletion, search-tree insert and two-child delete, and AVL rebalancing with the case named.
3
Prove the four bounds
Build-heap's Σ h/2ʰ, chaining's 1 + α, AVL's Fibonacci height, and union by rank's log n — each proved once, and each one the reason a later course can quote a cost without re-deriving it.
4
Choose, and say what you gave up
From an operation mix, pick among sorted array, hash table, AVL tree, heap and union–find, and name the operation the winner cannot answer at all.
Lessons
14 lessons
Sequences first, because their cost model is the vocabulary; then the three structures that trade a different thing for search — a heap trades order, a hash table trades order and worst case, a search tree trades constants; then balance, augmentation, and the one structure that is not a container at all.
Arrays, Linked Lists, and the Cost ModelCost one operation sequence on a dynamic array and on a doubly-linked list, and name the operation that decided it.Not marked
Stacks, Queues, and the Two-Stack QueueCount the stack moves in an enqueue/dequeue sequence and give the credit argument that bounds the total by 3m.Not marked
Priority Queues and Binary HeapsInsert and extract by sifting, read the array back as a tree, and check each operation’s comparisons against ⌊log₂ n⌋.Not marked
Building a Heap in Linear TimeEvaluate Σ ⌈n/2ʰ⁺¹⌉·h exactly for a given n and say why n inserts cost more than one bottom-up pass.Not marked
Hashing with ChainingCompute α and the expected search cost as exact fractions, then build the key set that degenerates h(k) = k mod m.Not marked
Open Addressing and Linear ProbingInsert, search and delete in a probing table leaving tombstones correctly, and read the counted probes against Knuth’s curve.Not marked
Resizing and the Load FactorCount the rehash cost of an insert/delete sequence under two threshold policies and identify the one that thrashes.Not marked
Binary Search TreesSearch, insert and delete including a two-child node, and tell the global invariant apart from the local check that passes on a tree that is not a search tree.Not marked
The Shape Problem and Random BSTsPredict a tree’s height from its insertion order, and produce one order that degenerates a key set and one that balances it.Not marked
Rotations and the AVL InvariantRotate at a chosen node and verify the in-order sequence is unchanged, then tabulate N(h) and bound the height at a given n.Not marked
AVL InsertionInsert a key sequence into an AVL tree naming the case at each rebalance, and compare the height with the plain tree on the same order.Not marked
Augmenting a TreeCompute rank and select by walking a size-annotated tree, and say which attributes can ride along and which cannot.Not marked
Union–FindRun a union/find sequence under each combination of the two rules and give the rank–height proof that union by rank bounds the depth.Not marked
Choosing a StructureCost an operation mix on every structure at once, rank them, and name what the winner cannot answer at all.Not marked
Recommended background
Discrete Mathematics in full, and by name: Big-O Notation, Analysing Iterative Algorithms, Recursion Trees and Amortised Analysis, Trees, Tree Traversals, Graph Representations, Hashing and Pseudorandom Numbers, and Linearity of Expectation.
Practice suggestions
Run the sequence before reading the bound. Every lab on this course counts an execution, and the number it prints is the answer for that sequence only. The bound is the lesson's claim about all of them.
When a cost is amortised, find the expensive operation. It is still there, it still happens, and the guarantee is about the total. A reader who cannot point at it has read the bound as “always fast”.
Break the structure deliberately. The degenerate key set, the sorted insertion order, the delete that empties a slot: each lab can produce the input that defeats its structure, and that input is the lesson.
What it does not cover
Red–black trees and B-trees. AVL stands in for balance, and B-trees are about disk — System Design's “The Height of a B-tree” costs one in I/O, which is the reason they exist.
Fibonacci heaps, and AVL deletion. Both are stated and neither is developed; the first changes Dijkstra's bound and no lesson here depends on the change.
The proof of union–find's α(n) bound. The statement is used; the proof is out of scope, and “Union–Find” says so in those words.
Cache-aware and persistent structures. The cost model here is the word RAM, where every access costs one.