Spring 2020

UC Berkeley

This is an introductory course to computer science theory, exploring the design and analysis of various algorithms, number theory, and complexity. The prerequisites include familiarity with mathematical induction, big-O notation, basic data structures, and programming in a standard language.

CS 170 is Berkeley’s introduction to the theory of computer science. In CS 170, we will study the design and analysis of graph algorithms, greedy algorithms, dynamic programming, linear programming, fast matrix multiplication, Fourier transforms, number theory, complexity, and NP-completeness.

The prerequisites for CS 170 are CS 61B and CS70. You will need to be comfortable with mathematical induction, big-O notation, basic data structures, and programming in a standard imperative language (e.g., Java/C/Python). Another “prerequisite” for doing well in the course is mathematical maturity, or the ability to think about and work with proof-based math (which CS70 can help build).

No data.

The required textbook is Algorithms by Dasgupta, Papadimitriou, and Vazirani, also known as DPV. Most readings will be from the textbook, and the relevant textbook chapters will be linked for each lecture. Any readings not from the textbook will be freely available as notes.

Reading available at Reading

Webcast available on YouTube at CS170 Spring 2020

Projects available at https://inst.eecs.berkeley.edu/~cs170/sp20/

No other materials available

Algorithms to Linear ProgrammingArithmeticBig-O notationBipartite MatchingCoefficient/value representationComplex numbersDepth-first search (DFS)DualityDynamic programmingFast Fourier transformFourier TransformGreedy AlgorithmInteger multiplicationKruskal's AlgorithmLinear ProgrammingMaster theoremMatrix MultiplicationMedian findingMinimum Spanning Tree (MST)Multiplicative UpdatesNP-completenessNetwork flow problemPaths in graphsPolynomial multiplicationRecurrence relationReductionsRoots of unitySamplingSearch problemSimplex AlgorithmSingle Source Shortest PathsSketchingStreamingStrongly connected componentsTopological sortingZero Sum Games