Computer Science › Algorithms & Software
AVL and red-black trees stay balanced by keeping at most 2 children per node — a B-tree instead lets each node hold many keys and many children, the specific shape that makes it the structure real databases and filesystems actually use.
A BST that alternates which coordinate it splits on at each level — the natural, already-familiar tree-search idea, extended to answer "which points fall inside this rectangle" far faster than checking every point.
The same PageRank already solved as a 4-page toy eigenvector problem — reimplemented the way Google's original paper actually describes computing it at scale: no eigendecomposition, just repeated matrix-vector multiplication until it settles.
Princeton's WordNet-style problem: given a directed acyclic graph of hypernym relationships, find the shortest ancestral path connecting any two nodes — two BFS traversals combined into one real answer.
Implement Dijkstra's algorithm for real, on a real weighted graph, backed by the heap already built — and verify its output against a graph small enough to check by hand.
Dijkstra explores blindly outward in every direction — A* adds a heuristic estimate of remaining distance, exploring toward the goal instead, and stays exact as long as that heuristic never overestimates.
Load a large dictionary into a trie, then search a letter grid for every valid word — the exact prefix-pruning trick a trie enables, and a hash-set-based version to measure why it isn't fast enough.
Princeton's own famous union-find assignment: model a grid of sites opening one at a time, and use union-find to answer, after every single opening, whether the grid now percolates top to bottom.
Build a real hash table from a plain array — your own hash function, your own collision handling, your own resizing — and put every guarantee that theory promised to an actual, measured test.
Every Big-O claim made across this entire curriculum, put to an actual timed test — measuring real running times against growing input sizes for the structures built in this lab, and checking whether the numbers actually behave the way the theory promised.
Part of the Computer Science curriculum.
AVL and red-black trees stay balanced by keeping at most 2 children per node — a B-tree instead lets each node hold many keys and many children, the specific shape that makes it the structure real databases and filesystems actually use.
A BST that alternates which coordinate it splits on at each level — the natural, already-familiar tree-search idea, extended to answer "which points fall inside this rectangle" far faster than checking every point.
The same PageRank already solved as a 4-page toy eigenvector problem — reimplemented the way Google's original paper actually describes computing it at scale: no eigendecomposition, just repeated matrix-vector multiplication until it settles.
Princeton's WordNet-style problem: given a directed acyclic graph of hypernym relationships, find the shortest ancestral path connecting any two nodes — two BFS traversals combined into one real answer.
Implement Dijkstra's algorithm for real, on a real weighted graph, backed by the heap already built — and verify its output against a graph small enough to check by hand.
Dijkstra explores blindly outward in every direction — A* adds a heuristic estimate of remaining distance, exploring toward the goal instead, and stays exact as long as that heuristic never overestimates.
Load a large dictionary into a trie, then search a letter grid for every valid word — the exact prefix-pruning trick a trie enables, and a hash-set-based version to measure why it isn't fast enough.
Princeton's own famous union-find assignment: model a grid of sites opening one at a time, and use union-find to answer, after every single opening, whether the grid now percolates top to bottom.
Build a real hash table from a plain array — your own hash function, your own collision handling, your own resizing — and put every guarantee that theory promised to an actual, measured test.
Every Big-O claim made across this entire curriculum, put to an actual timed test — measuring real running times against growing input sizes for the structures built in this lab, and checking whether the numbers actually behave the way the theory promised.