Berkeley CS 170: Efficient Algorithms and Intractable Problems
CS 170 is Berkeley's algorithms course: divide and conquer, graph algorithms, greedy methods, dynamic programming, linear programming, and NP-completeness. It's the theory core of the upper division, building directly on CS 61B's data structures and CS 70's proof skills.
Fennie is independent and not affiliated with UC Berkeley. This is an unofficial study guide.
What makes it hard
170 is where proof-writing and algorithm design fuse: homework asks you to invent an algorithm, prove it correct, and analyze its runtime, and partial understanding produces zero-credit attempts. Exam medians are famously modest, and the dynamic-programming and reduction questions are the classic separators.
What you'll cover
- • Divide and conquer and recurrences
- • Graph algorithms and shortest paths
- • Greedy algorithms
- • Dynamic programming
- • Linear programming and network flow
- • NP-completeness and reductions
The CS 170 study guide
How to study for Berkeley CS 170, step by step.
- 1
Re-sharpen CS 70 proof skills before the semester
170 assumes you can write induction and exchange arguments cleanly. If your proof muscles atrophied since 70, rebuild them in the first two weeks; the homework assumes them from problem one.
- 2
Attempt every homework problem alone first
The learning is in the struggle before the study-group discussion. Give each problem a real solo attempt, then collaborate within course policy. Students who skip the solo phase consistently underperform on exams.
- 3
Drill dynamic programming as a formula: state, recurrence, base case
DP questions decide grades in 170. For every practice problem, write the subproblem definition explicitly before any code or recurrence; naming the state precisely is the hard part.
- 4
Practice reductions in both directions
For NP-completeness, internalize the direction of a reduction and rehearse the standard ones from lecture. Exam reductions are variations on patterns you can train deliberately.
- 5
Calibrate with past exams early, not just before finals
170 exam problems are novel by design, so the skill is solving fresh problems under time pressure. Start working old exams from the archives mid-semester to build that muscle gradually.
Today
Today's CS 170 plan
What a Fennie Daily Plan looks like for CS 170. Yours is built from your own syllabus and adapts every day to your deadlines and progress.
First plan free, no card required. Fennie is independent and unaffiliated with your school.
FAQ
Is CS 170 hard?
It's one of the harder required CS courses because it fuses proof-writing with algorithm invention: you design something new and prove it correct on every homework. Students solid from CS 70 adapt within weeks; rusty proof skills make the start rough.
What's the hardest part of CS 170?
Most students point to dynamic programming and NP-completeness reductions. Both are trainable: DP rewards explicitly defining the subproblem before anything else, and reductions follow patterns that practice makes recognizable.
How do I prepare for CS 170?
Be honest about your CS 70 proof fluency and 61B data-structure recall; 170 leans on both immediately. Working a few induction and graph proofs before the semester starts removes most of the early shock.
More Berkeley courses
CS 61A: The Structure and Interpretation of Computer Programs
CS 61A is Berkeley's legendary intro CS course, taught primarily in Python with excursions into Scheme and SQL. It emphasizes abstraction (higher-order functions, recursion, object-oriented programming, and interpreters) and it's the first course in the CS 61 series that every CS and Data Science student takes.
CS 61B: Data Structures
CS 61B is Berkeley's data structures course, taught in Java, covering lists, trees, hashing, graphs, sorting, and asymptotic analysis. It's the second course in the 61 series and the one most cited in industry-interview prep. Its projects, including the famous build-your-own-world and Gitlet (build a mini Git), are substantial software engineering exercises.
CS 70: Discrete Mathematics and Probability Theory
CS 70 is Berkeley's discrete math and probability course, required for the CS major, covering proofs, graph theory, modular arithmetic, RSA, polynomials, counting, and a substantial probability unit. It's the theory gateway and, by reputation, the hardest lower-division course in the major.
CS 61C: Great Ideas of Computer Architecture (Machine Structures)
CS 61C completes Berkeley's 61 series, going below the abstraction line: C programming, RISC-V assembly, CPU datapaths and pipelining, caches, virtual memory, and parallelism. It's required for the CS and EECS majors and is the course where software students finally see what the hardware is doing.