Stanford CS106B — Programming Abstractions in C++

From-scratch solutions to the CS106B assignment sequence (recursion, backtracking, ADTs & sorting, priority queues, Huffman coding, and graph pathfinding) — an independent, from-skeleton implementation of CS106B — Programming Abstractions in C++ (Stanford University), part of a csdiy.wiki full-catalog build.

Overview

CS106B is Stanford's second programming course: recursion, algorithmic problem solving, abstract data types, and the classic data structures and algorithms built on top of them. This repository implements the algorithmic core of the full assignment sequence — a1 through a7 — in modern C++20, each with its own test suite, and verifies every one on the console on a Windows / MSYS2 GCC box (no Qt, no GPU).

The catch: CS106B ships against the Qt-based Stanford C++ Library, which does not build on this machine. Rather than fake anything, this repo vendors a clean-room, non-graphical re-implementation of exactly the library surface the algorithms need (Vector, Grid, Map, Set, HashMap, Queue, Stack, PriorityQueue, Lexicon, Bit, error(), …) plus a headless SimpleTest harness with the same PROVIDED_TEST / STUDENT_TEST / EXPECT_* / TIME_OPERATION macros as the real thing. See lib/vendor-stanford/README.md. Only the genuinely graphical pieces (on-screen GWindow rendering, the debugger walkthrough) are left as documented Qt-only partials — their algorithms are still implemented and tested headlessly.

Results (measured on Windows 11, MSYS2 GCC 14.2, -std=c++20 -O2, CPU-only)

Every assignment is console-verified. 118 tests pass, 0 fail. Raw captured output for each is in results/.

Assignment	Focus	Console result (measured)
a1 — Welcome to C++!	recursion, grids, strings	20/20 pass
a2 — Fun with Collections	ADTs, cosine similarity, BFS flood	15/15 pass
a3 — Recursion!	procedural / graphical / backtracking recursion	25/25 pass
a4 — Recursion to the Rescue!	backtracking (matching, dominating set)	17/17 pass
a5 — Data Sagas	k-way merge, own-memory binary heap, streaming top-k	23/23 pass
a6 — Huffman Coding	binary trees + priority queues, compression	9/9 pass
a7 — Trailblazer	graphs: BFS, Dijkstra, A*, Kruskal MST	9/9 pass

Some real numbers the tests actually measure:

• a5 HeapPQueue is a from-scratch, 1-indexed binary min-heap over a manually managed dynamic array (no std::vector). n enqueues + n dequeues scale as O(n log n): 17 ms → 35 ms → 88 ms → 192 ms for n = 50k → 100k → 200k → 400k.
• a5 Streaming top-k finds the k heaviest of a stream in O(k) space and O(n log k) time — near-linear in n at fixed k: 4.9 ms → 10.3 ms → 20.0 ms → 39.8 ms for n = 50k → 400k.
• a5 Combine (k-way merge) runs in O(n log k): at fixed n = 200k, growing k by 4× each step stays nearly flat (20 → 36 → 58 → 60 ms), the signature of the log-k factor.
• a6 Huffman achieves real, lossless compression: a 1,800-char English sample goes from 14,400 bits → 6,560 bits (45% of the original) and decompresses back bit-for-bit.
• a7 Trailblazer verifies optimality directly: Dijkstra returns cost 5 where BFS's fewest-edges route costs 12; A* matches Dijkstra's cost on grids (Manhattan distance 10); Kruskal's MST total is the hand-checked minimum (8).

Implemented assignments

• a1 — Welcome to C++! — onlyConnectize (recursive consonant filter), Thue-Morse "playing fair" sequences, Abelian sandpiles (recursive toppling), and a turtle-graphics Plotter (line-segment interpreter).
• a2 — Fun with Collections — Rosetta Stone language ID (k-gram profiles, normalization, top-k via PriorityQueue, cosine similarity) and Rising Tides (multi-source BFS flood-fill on an elevation grid).
• a3 — Recursion! — Sierpinski triangle (records the triangles it draws), Human Pyramids (memoized weight recursion), "What Are You Doing?" (all emphasis patterns of a sentence), and Shift Scheduling (exhaustive value maximization).
• a4 — Recursion to the Rescue! — Matchmaker (perfect matching + maximum weight matching by backtracking) and Disaster Planning (minimum dominating-set search with smart branching).
• a5 — Data Sagas — combine (O(n log k) k-way merge), HeapPQueue (the data-structure implementation assignment: a binary heap doing all its own memory management), and topK (streaming top-k client of the heap).
• a6 — Huffman Coding — buildHuffmanTree, encodeText/decodeText, flattenTree/unflattenTree, and a full compress/decompress pipeline over a Huffman coding tree.
• a7 — Trailblazer — breadthFirstSearch, dijkstrasAlgorithm, aStar (with an admissible straight-line heuristic), and kruskal (minimum spanning tree via union-find).

Graphical parts (documented Qt-only partials)

A handful of pieces render to a Qt GWindow and cannot run on this Qt-less machine. For each, the algorithm is implemented and verified headlessly; only the on-screen drawing is out of scope:

• a1 Plotter / a3 Sierpinski — the drawing logic is fully implemented and tested by capturing the exact line segments / triangles that would be drawn; only the literal GWindow pixels are Qt-only.
• a5 Array Exploration — this part is a debugger walkthrough (set a breakpoint, inspect out-of-bounds array memory in Qt Creator, write up answers). It has no autogradable code deliverable; it is inherently IDE/GUI-only.
• a5 / a7 demo apps — the interactive "explore these data sets" and animated maze visualizers are GUI front-ends over the same combine / HeapPQueue / topK / pathfinding code that the console tests already exercise.

Nothing is faked: every number in the results table above comes from a real compile-and-run on this machine.

Project structure

cs106b/
├── assignments/
│   ├── a1-welcome-cpp/      OnlyConnect, PlayingFair, Sandpiles, Plotter
│   ├── a2-collections/      RosettaStone, RisingTides
│   ├── a3-recursion/        Sierpinski, HumanPyramids, WhatAreYouDoing, ShiftScheduling
│   ├── a4-backtracking/     Matchmaker, DisasterPlanning
│   ├── a5-data-sagas/       Combine, HeapPQueue, TopK
│   ├── a6-huffman/          Huffman (+ EncodingTree)
│   └── a7-trailblazer/      Trailblazer (+ WeightedGraph)
├── lib/
│   ├── vendor-stanford/     clean-room non-graphical Stanford C++ library subset
│   └── simpletest/          headless SimpleTest harness (PROVIDED_TEST/EXPECT/…)
├── results/                 captured console output of each test run
├── tools/build_and_test.sh  compile one assignment + run its tests
└── LICENSE

How to run

Requires a C++20 compiler (developed with MSYS2 GCC 14.2 on Windows). Each assignment is a self-contained set of .cpp files whose main.cpp runs its SimpleTest suite. The helper script compiles an assignment against the vendored library and runs it:

# Build and run one assignment's test suite:
bash tools/build_and_test.sh assignments/a6-huffman

# Run them all:
for a in assignments/a*/; do bash tools/build_and_test.sh "$a"; done

Or invoke the compiler directly (this is exactly what the script does):

g++ -std=c++20 -O2 -Wall -static -static-libgcc -static-libstdc++ \
    -Ilib/vendor-stanford -Ilib/simpletest -Iassignments/a6-huffman \
    assignments/a6-huffman/*.cpp lib/simpletest/SimpleTest.cpp -o run.exe
./run.exe

The -static flags work around a MSYS2 binutils bug that segfaults when linking libstdc++ dynamically for these programs.

Verification

Every assignment's main() calls runSimpleTests(), which runs all PROVIDED_TEST and STUDENT_TEST cases and returns the number of failures as the process exit code. The captured runs live in results/:

$ bash tools/build_and_test.sh assignments/a5-data-sagas
...
Summary: 23 passed, 0 failed, 23 total.
ALL TESTS PASSED.

The TIME_OPERATION timing tests in a5 print wall-clock scaling that confirms the required big-O bounds (O(n log k) for combine and top-k, O(n log n) for the heap), and a6's compression test prints the measured bit-savings. Those numbers are quoted in the Results section above and reproduced verbatim in results/.

Tech stack

• Language: C++20
• Toolchain: MSYS2 GCC 14.2 (Windows), -O2, static linking
• Libraries: a vendored, clean-room, non-graphical subset of the Stanford C++ Library (backed by the C++ standard library) + a headless SimpleTest harness. No Qt, no third-party dependencies.

Key ideas / what I learned

• Recursion in every flavor — procedural (sandpiles, Thue-Morse), graphical (Sierpinski), exhaustive enumeration (emphasis patterns, shift scheduling), and backtracking (matching, dominating sets) — and when memoization is worth it.
• Choosing the ADT to fit the problem — PriorityQueue for top-k selection, Queue for BFS, Map/Set for frequency and adjacency, and building your own when the interface demands it.
• Implementing a data structure from raw memory — a binary heap on a hand-managed, geometrically-growing dynamic array, with correct destructor and no leaks; the 1-indexed parent/child arithmetic that makes it work.
• Streaming algorithms — solving top-k in O(k) space by keeping only the best k seen so far in a bounded min-heap, so the input never has to fit in memory.
• Trees + greedy = compression — Huffman's optimal prefix codes, and serializing/deserializing a tree so a compressed file is self-describing.
• The unifying shape of graph search — BFS, Dijkstra, and A* are one algorithm with three frontier policies; an admissible heuristic keeps A* optimal; Kruskal + union-find builds a minimum spanning tree.

Credits & license

Based on the assignments of CS106B — Programming Abstractions in C++ by Keith Schwarz and the CS106B teaching staff at Stanford University. This repository is an independent educational reimplementation; all course materials, assignment specifications, and the original Stanford C++ Library belong to their respective authors. The vendored library here is a clean-room re-implementation, not the Stanford source. Original code in this repo is released under the MIT License.