Polynomial multiplication

Big-O notation

Integer multiplication

Master theorem

Median finding

Coefficient/value representation

Roots of unity

Topological sorting

Paths in graphs

Greedy Algorithm

Kruskal's Algorithm

Linear Programming

Simplex Algorithm

Bipartite Matching

Zero Sum Games

Search problem

Reductions

Sampling

Streaming

Fast Fourier transform

Arithmetic

Recurrence relation

Matrix Multiplication

Complex numbers

Fourier Transform

Depth-first search (DFS)

Strongly connected components

Single Source Shortest Paths

Dynamic programming

Algorithms to Linear Programming

Duality

Multiplicative Updates

NP-completeness

Sketching

Minimum Spanning Tree (MST)

Network flow problem

CS 170: Efficient Algorithms and Intractable Problems UC Berkeley Spring 2020 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](https://en.wikipedia.org/wiki/Mathematical_maturity), or the ability to think about and work with proof-based math (which CS70 can help build). The required textbook is [Algorithms](http://cseweb.ucsd.edu/~dasgupta/book/index.html) 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.

CS 170: Efficient Algorithms and Intractable Problems

Data Structures and Algorithms

Theoretical Computer Science

Polynomial multiplication

1 courses cover this concept

CS 170: Efficient Algorithms and Intractable Problems