Computer Science 170 — Efficient Algorithms and Intractable Problems (4 Units)

Course Overview

Summary

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.

Prerequisites

  • CS61B, 70

Topics Covered

  • Designing and analyzing algorithms
  • Lower bounds
  • Divide and Conquer Problems
  • Search problems
  • Graph Problems
  • Greedy Algorithms
  • Linear Programming
  • Dynamic Programming
  • NP-completeness

Workload

Course Work

  • Weekly problem set
  • 1 programming assignment
  • 2 Midterms, 1 Final

Time Commitment

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.

What next?

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

Additional Comments/Tips

Start early, form a study group. Practice builds intuition.

The book problems are especially useful for midterm review.

Last edited: Summer 2020