Implementations of the five CS170 Spring 2026 coding problems, plus a
reproducible autograder harness and a demo. Every function is written from
scratch (no graph/FFT library calls inside the algorithms — the official
autograders ban them) and is verified against the exact otter @test_case
functions shipped in the course notebooks.
code/
├── hw02_quickselect/ quick_select.py + solved quick_select.ipynb
├── hw03_dfs_scc/ dfs_scc.py + solved dfs-scc.ipynb
├── hw04_shortest_paths/ shortest_paths.py + solved shortest-paths.ipynb
├── hw05_edit_distance/ edit_distance.py + solved edit-dist.ipynb
├── hw07_fft/ fft.py + solved fft.ipynb
├── demo_results.py end-to-end demo, writes ../results/
└── run_autograders.py runs the official otter tests locally
Each *.py module is a clean, importable standalone implementation; the
*.ipynb is the official course notebook with our solution injected into the
stub cells (ready to submit / rerun).
| Module | Function(s) | Algorithm | Autograder |
|---|---|---|---|
hw02_quickselect |
quick_select |
randomized quickselect, expected O(n) | q1 |
hw03_dfs_scc |
dfs_path, get_pre_post, reverse_graph, find_SCCs |
iterative DFS + Kosaraju–Sharir SCC | q1.1, q1.2, q2.1, q2.2 |
hw04_shortest_paths |
dijkstra, bellman_ford |
Dijkstra (heap) & Bellman-Ford (with neg-cycle detection) | q1, q2 |
hw05_edit_distance |
edit_distance |
O(nm) DP + alignment backtrace | edit_distance |
hw07_fft |
roots_of_unities, dft_naive, fft, ifft, poly_multiply |
recursive radix-2 FFT | q1.1–q1.4 |
All implementations are iterative where recursion depth would matter (DFS/SCC run on graphs up to 1000 nodes without hitting Python's recursion limit).
# 1. Fast, self-contained sanity tests (no large fixtures needed):
python -m pytest tests/ # 12 checks, < 1s
# 2. Full official autograders (needs the course fixtures):
git clone https://github.com/Berkeley-CS170/cs170-sp26-coding
python code/run_autograders.py --coding cs170-sp26-coding --quiet
# -> results/autograder_results.txt : 12/12 checks passed
# 3. Demo on real inputs (writes results/, generates the FFT figure):
python code/demo_results.pyThe last recorded run: 12/12 official autograder checks pass — see
../results/autograder_results.txt.
The large official test fixtures — hw3/generated_testcases.pkl (6.5 MB) and
hw5/inputs1.py (0.5 MB) — are not committed (they are course-owned data,
.gitignored). run_autograders.py reads them directly from a clone of the
official Berkeley-CS170/cs170-sp26-coding
repo.