Master every trace,
one array at a time.
Long-form explanations with living animations for every algorithm in the course — and the official practice assignments rebuilt as interactive exercises that check your work, cell by cell, right in the browser.
Exam readiness
Weights: exercises 40 · topics 25 · quizzes 20 · flashcards 15 — quiz weight redistributes until your first quiz
Course topics
Follows the lecture — Union-Find all the way to string sorts.
Union-Find & Dynamic Connectivity
Four implementations of one tiny API — quick-find, quick-union, weighted quick-union and path compression — and why the last one turns 30 years of computing into 6 seconds.
Stacks, Queues & Deques
The first data types of the course: LIFO and FIFO collections built three ways — fixed array, resizing array, linked list — plus the amortized analysis that makes doubling free.
Analysis of Algorithms
Predict performance with the scientific method: run experiments, hypothesize a power law T(N) ~ a·N^b, and confirm it with the doubling test — then explain it with tilde notation and cost models.
Elementary Sorts
Selection, insertion and shellsort: the trace conventions the exam demands, the total order behind __lt__, and why a few long-distance moves beat many adjacent ones.
Mergesort
Divide in half, sort each half recursively, merge: a guaranteed N lg N, stable sort whose only sin is the auxiliary array — plus bottom-up and k-way variants the assignments demand.
Quicksort
Partition in place, sort each side — the sort that shows up on every exam
Priority Queues & Heapsort
Binary heaps, delete-the-max traces, the 3-heap, and heapsort
Symbol Tables & BSTs
The key-value API, binary search trees, compare counting, traversals, Hibbard deletion
Balanced Search Trees
2-3 trees → left-leaning red-black BSTs: rotations, color flips, and the guarantee
Hashing
Compute the index from the key: separate chaining, linear probing, load factors, tombstones
Undirected Graphs
Adjacency lists, BFS, DFS, and connected components
Directed Graphs
Digraph traversals, topological order, cycles, and strong components
MST & Shortest Paths
Edge-weighted graphs, Kruskal, Prim, and Dijkstra
String Sorts
Key-indexed counting, LSD, MSD, and 3-way string quicksort
Exam Survival Guide
How traces are graded, the course’s Python idioms, and a 3-day plan
Practice assignments
The official sheets, rebuilt as validated interactive exercises.
Assignment 1 · Union-Find
Trace quick-find and quick-union on the classic 10-site sequence (id[] + array-access counts), find the bug in an intuitive union(), and decide which id[] arrays weighted quick-union can never produce.
Assignment 2 · Stacks, Queues, and Deques
LIFO vs FIFO, pop on an empty stack, a stack that prints binary digits, the classic queue-reversal fragment, and two real implementation tasks: the resizable stack with `usedSpace` and the doubly-linked-list deque — both judged by running the official Python test snippets in your browser.
Assignment 3 · Complexity and ThreeSum
Sort twelve functions into ascending Θ-groups, analyse the N² log N 3-sum algorithm and its doubling factors versus brute force, and compare iterative and recursive Fibonacci in tilde notation.
Assignment 4 · Elementary Sorting
Trace selection sort, insertion sort and shellsort by hand on the lecture letter arrays, decide which of the two sorts wins on identical and on reverse-ordered input, get the __lt__ student ordering right, and know the two practical insertion-sort improvements.
Assignment 5 · Mergesort Variants
Trace top-down mergesort on SOMEIMPLETEST one merge at a time, then analyse k-way mergesort: total cost ~N·k·log_k N, the pass/compare arithmetic that makes k = 3 marginally optimal, and a Stopwatch experiment to validate the hypothesis.
Assignment 6 · Complexity, Priority Queues, and Quicksort
Fit a power law to a doubling table and extrapolate to N = 200,000, classify six recursive functions by order of growth, simulate a max-PQ op sequence, rebuild a stack from a PQ, delete-the-max on a ternary heap, and trace partition() plus full quicksort on EASYQUESTION.
Assignment 7 — Binary Search Trees
Build a BST from EASYQUESTION, count compares, discover all worst- and best-case insertion orderings of A X C S E R H, traverse a given tree, and write the perfect-balance insertion program — validated in-browser against binary search itself.
Assignment 8 — Red-Black BSTs
Reconstruct a left-leaning red-black tree: deduce the suppressed key, prove which links must be red, count rotations for three inserts — then implement deleteMin/deleteMax yourself in the official RedBlack.py, judged by output and by invariant checks.
Assignment 9 — Hashing and Breadth-First Search
Trace a linear-probing hash table, decide which final arrays are reachable at all, run BFS on the assignment graph, and prove an invariant about vertices sharing the BFS queue.
Assignment 10 — Minimum Spanning Trees and Shortest Paths
Decide which weights the variable edges x, y, z can carry while staying in an MST (cycle/bottleneck arguments), then reverse-engineer Dijkstra's PQ order and edge weights from a snapshot of distTo/edgeTo.
Assignment 11 — String Sorts
Key-indexed counting by hand, a full LSD radix trace, the first MSD partition level, and the design decisions of 3-way string quicksort.