Skip to content

Latest commit

 

History

History

code

README.md

CS170 Coding Solutions

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.

Layout

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).

What each solves

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).

Verifying

# 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.py

The last recorded run: 12/12 official autograder checks pass — see ../results/autograder_results.txt.

Note on fixtures

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.