CS170 — Efficient Algorithms and Intractable Problems (Solutions)

Rigorous written solutions to every homework, plus implemented and autograder-verified code for the algorithmic problems — an independent, from-scratch treatment of CS170 — Efficient Algorithms and Intractable Problems (UC Berkeley), part of a csdiy.wiki full-catalog build.

Overview

CS170 is Berkeley's upper-division algorithms course: divide & conquer, graph algorithms, greedy methods, dynamic programming, the FFT, linear programming and duality, zero-sum games, NP-completeness and reductions, and randomized / streaming / hashing algorithms. This repository contains:

• homeworks/ — complete, rigorous written solutions to all 14 Spring 2026 homeworks (algorithm + correctness proof + running-time analysis), one Markdown file per HW.
• code/ — clean Python implementations of the five coding problems, each verified against the exact official otter autograder shipped in the course notebooks, plus a reproducible test harness and a demo that runs every algorithm on real inputs.

Everything here runs on a CPU-only Windows machine with Python 3.11.

Results (measured on CPU, Python 3.11)

Official coding autograders — 12/12 checks pass. Each check runs the exact @test_case embedded in the course notebook's metadata.otter.tests against our implementation (see results/autograder_results.txt):

Assignment	What it does	Result (measured)
HW2 quickselect	randomized order-statistic selection, expected O(n)	q1 PASS (correctness + no-sort + beats sorted() on 200k-element arrays)
HW3 DFS/SCC	DFS path, pre/post numbers, graph reverse, Kosaraju–Sharir SCC	q1.1, q1.2, q2.1, q2.2 PASS (graphs up to 1000 nodes)
HW4 shortest paths	Dijkstra + Bellman-Ford (with neg-cycle detection)	q1, q2 PASS (Dijkstra to 10 000 nodes; Bellman-Ford correctness incl. neg cycles)
HW5 edit distance	O(nm) DP global alignment + backtrace	edit_distance PASS (200 random 250–500-char pairs vs pylev)
HW7 FFT	roots of unity, naive DFT, recursive FFT, inverse FFT	q1.1–q1.4 PASS (correctness + uses-given-roots + O(n log n) speed)

Demo run on real inputs (from results/demo_run.txt):

• quickselect finds the median of 2,000,000 random ints, 3.4× faster than sorted(), value verified;
• SCC decomposition and DFS path correct on a hand-checked 7-node graph;
• Dijkstra and Bellman-Ford both return length 431 on a 400-node random graph, matching the NetworkX reference;
• edit-distance alignment of EXPONENTIAL/POLYNOMIAL gives cost 6 (matches pylev);
• FFT multiply of (1+2x+3x²)(4+5x+6x²) = [4, 13, 28, 27, 18] (exact), and FFT multiplies two degree-8192 polynomials in ~1.2 s.

Figure — FFT vs naive polynomial multiplication (log–log), generated by the demo:

Several written-solution numbers were also cross-checked with SciPy/NumPy: the backprop gradients (HW6), the jeweler LP optimum (15,20) → $1500 and its sensitivity ranges (HW9), the weighted rock-paper-scissors and domination game values (HW11), and the 7/8 MAX-3-SAT tightness example (HW14).

Implemented assignments

Written solutions (all 14 homeworks):

• HW1 — asymptotic order of growth; linear-time & matrix-power step counting
• HW2 — divide & conquer: key/lock matching, max-subarray, monotone matrices, werewolves
• HW3 — graphs: skyline, ancestor queries, centroid decomposition, path counting, 2SAT via SCC
• HW4 — greedy: Horn-SAT, ternary Huffman, local search, bounded-negative shortest path
• HW5 — DP: motel choosing, coin combinations, EDF scheduling, egg drop
• HW6 — backpropagation by hand; polynomial multiplication & polynomial-from-roots; DSP
• HW7 — inverse FFT, 3-sum via FFT, cyclic correlation, parallel FFT
• HW8 — parallel algorithms (prefix/scan), residual connections & gradient stability
• HW9 — linear programming & duality, multicommodity flow, VC/IS duality, integrality gaps
• HW11 — LP/games: coin-change ILP, zero-sum games, dominated strategies, Klee-Minty
• HW12 — multiplicative weights / experts, regret bounds, halving
• HW13 — NP-completeness: reductions, TSP variants, 3SAT→ILP, halting
• HW14 — dealing with NP-hardness: (3,3)-SAT, 3D matching, 7/8-approx, √n-coloring
• HW15 — hashing & streaming: universal/pairwise-independent hashing, reservoir sampling, Boyer–Moore majority

Verified code (5 coding problems): quickselect, DFS/SCC, Dijkstra & Bellman-Ford, edit distance, FFT — all passing the official autograders.

(There is no HW10 in the course schedule, and this iteration of CS170 has no separate multi-week coding "project" — the graded implementation work is the five homework coding notebooks, all completed here.)

Project structure

cs170/
├── homeworks/            # 14 written HW solutions (Markdown) + index
│   ├── hw01.md … hw15.md
│   └── README.md
├── code/                 # 5 verified coding solutions
│   ├── hw02_quickselect/     quick_select.py  + solved .ipynb
│   ├── hw03_dfs_scc/         dfs_scc.py       + solved .ipynb
│   ├── hw04_shortest_paths/  shortest_paths.py+ solved .ipynb
│   ├── hw05_edit_distance/   edit_distance.py + solved .ipynb
│   ├── hw07_fft/             fft.py           + solved .ipynb
│   ├── demo_results.py       # runs everything on real inputs -> results/
│   ├── run_autograders.py    # runs the official otter tests locally
│   └── README.md
├── tests/                # fast self-contained pytest suite (12 checks)
├── results/              # measured evidence: autograder log, demo log, figure
├── requirements.txt
└── LICENSE

How to run

# Python 3.11. Reuse the shared csdiy env or create your own:
python -m pip install -r requirements.txt

# 1) Fast sanity tests (no external fixtures, < 1 second):
python -m pytest tests/

# 2) Reproduce the official autograders (fetch the course fixtures first):
git clone https://github.com/Berkeley-CS170/cs170-sp26-coding
python code/run_autograders.py --coding cs170-sp26-coding --quiet
#    -> writes results/autograder_results.txt  (12/12 checks passed)

# 3) Run the demo on real inputs and regenerate the FFT figure:
python code/demo_results.py
#    -> writes results/demo_run.txt and results/fft_vs_naive.png

Verification

• Fast tests: pytest tests/ runs 12 property/spot checks (quickselect vs sorted, SCC on a known graph, Dijkstra≡Bellman-Ford≡NetworkX on random graphs, edit distance vs pylev, FFT vs numpy.fft, IFFT∘FFT = identity) in under a second.
• Authoritative: code/run_autograders.py loads each notebook's embedded otter @test_case and runs it against our code — 12/12 pass, logged to results/autograder_results.txt. This is the same code the course uses to grade, so passing it is real evidence of correctness (and, for quickselect / Dijkstra / FFT, of the required asymptotic speed).
• Written proofs: load-bearing numeric claims are independently confirmed with SciPy/NumPy (see Results).

Tech stack

Python 3.11 · NumPy · SciPy · NetworkX (test graphs only — never called inside the algorithms) · Matplotlib · pytest · pylev · otter-grader.

Key ideas / what I learned

• Divide & conquer beyond sorting: quickselect's expected-linear analysis, monotone-matrix search with per-level accounting, and skyline merging.
• The DFS toolkit: pre/post interval nesting powers ancestor queries, topological order, and Kosaraju–Sharir SCCs — and SCCs solve 2SAT in linear time.
• FFT as evaluation↔interpolation: the same butterfly recursion multiplies polynomials, computes correlations/convolutions, and runs in O(n log n); the inverse is just the transform on conjugate roots divided by n.
• LP duality as a unifying lens: vertex cover ↔ matching, independent set ↔ edge cover, zero-sum game values via primal/dual, and integrality gaps that bound how far LP relaxations can drift from the integer optimum.
• NP-hardness via gadget reductions (3SAT→ILP, (3,3)-SAT→3D-matching) and what to do next: randomized 7/8-approximation, √n-coloring, and hardness of approximation by gap amplification.
• Streaming/hashing: universal vs pairwise-independent hashing, reservoir sampling, and Boyer–Moore majority — big computations in O(log) space.

Credits & license

Based on the assignments of CS170 — Efficient Algorithms and Intractable Problems by L. Chen & U. Vazirani (UC Berkeley, Spring 2026; cs170.org). Coding notebooks and autograders are from the official Berkeley-CS170/cs170-sp26-coding repository. This repository is an independent educational reimplementation; all course materials, problem statements, datasets, and autograder fixtures belong to their original authors and are not redistributed here (the course PDFs and large fixtures are .gitignored — download them from the course). Original code and write-ups in this repo are released under the MIT License.