Computer Science 170 — Efficient Algorithms and Intractable Problems (4 Units)
CS 170 is an introductory course to theoretical computer science and surveys a variety of algorithm paradigms. Central concepts are algorithm design, algorithmic proofs, and running time analysis. The course also serves as an intro to complexity classes, exploring NP-completeness. The format of assignments is typically written problem sets, with pseudocode expected rather than compilable computer code.
- CS61B, 70
- Designing and analyzing algorithms
- Lower bounds
- Divide and Conquer Problems
- Search problems
- Graph Problems
- Greedy Algorithms
- Linear Programming
- Dynamic Programming
- Weekly problem set
- 1 programming assignment
- 2 Midterms, 1 Final
3 hours of lectures, 1 hour of discussion and 10-15 hours of problem set.
Choosing the Course
When to take
After taking CS70 and CS61B, usually sophomore or junior year.
- CS188: Expands upon graph searches and approximate solutions to computationally intractable problems.
- CS172: More on NP-completeness and time/space complexity.
- CS174: Randomized Algorithms.
- CS176: More focus on string algorithms.
- CS270: Goes into more modern algorithms problems.
Usefulness for Research or Internships
Very useful, as many interview questions require knowledge from this course.
170 is likely a prerequisite for any CS theory research.
Start early, form a study group. Practice builds intuition.
The book problems are especially useful for midterm review.
Last edited: Summer 2020