Warning: Fall 2019 website is under construction. There may be misleading information from past semesters on this website, which may be different from the Fall 2019 offering of the course.
We will remove this warning when the information on this website is accurate.

Materials

Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

1
Lec 1
1/22

Intro, O() notation, Integer multiplication

Lec 2
1/24

Matrix multiplication, Master theorem

2
Lec 3
1/29

FFT

Lec 4
1/31

FFT, Graphs

3
Lec 5
2/5

DFS, Graph Decomposition

Lec 6
2/7

Shortest Paths

4
Lec 7
2/12

Shortest Paths, Bellman-Ford

Midterm 1
2/14

No lecture on 2/14

§ Up to Djikstra's Algorithm on 2/7

5
Lec 8
2/19

Greedy Algorithms, MST

Lec 9
2/21

Greedy Algorithms

6
Lec 10
2/26

Dynamic Programming

Lec 11
2/28

Dynamic Programming

7
Lec 12
3/5

Dynamic Programming

Lec 13
3/7

Dynamic Programming

8
Lec 14
3/12

Linear Programming

Lec 15
3/14

Linear Programming

9
Lec 16
3/19

Linear Programming

Lec 17
3/21

Linear Programming

10
Spring Break
Spring Break
11
Midterm 2
4/3

No lecture on 4/2

§ Up to 3/19

Lec 18
4/4

Linear Programming

12
Lec 19
4/9

Multiplicative Weights

Lec 20
4/11

Follow the Regularized Leader

13
Lec 21
4/16

Streaming I

Lec 22
4/18

Streaming II

14
Lec 23
4/23

Search problems, Complexity Theory

§

notes (primary), 8.1 (secondary), slides, webcast

Lec 24
4/25

NP-Completeness

§

notes (primary), 8.2, 8.3 (secondary), webcast

15
Lec 25
4/30

Coping with NP-completeness

§

9.2, webcast

Lec 26
5/2

Coping with NP-completeness

§

9.2, webcast

16
RRR Week
RRR Week
Lec 1
1/22

Intro, O() notation, Integer multiplication

Lec 2
1/24

Matrix multiplication, Master theorem

Lec 3
1/29

FFT

Lec 4
1/31

FFT, Graphs

Lec 5
2/5

DFS, Graph Decomposition

Lec 6
2/7

Shortest Paths

Lec 7
2/12

Shortest Paths, Bellman-Ford

Lec 8
2/19

Greedy Algorithms, MST

Lec 9
2/21

Greedy Algorithms

Lec 10
2/26

Dynamic Programming

Lec 11
2/28

Dynamic Programming

Lec 12
3/5

Dynamic Programming

Lec 13
3/7

Dynamic Programming

Lec 14
3/12

Linear Programming

Lec 15
3/14

Linear Programming

Lec 16
3/19

Linear Programming

Lec 17
3/21

Linear Programming

Lec 18
4/4

Linear Programming

Lec 19
4/9

Multiplicative Weights

Lec 20
4/11

Follow the Regularized Leader

Lec 21
4/16

Streaming I

Lec 22
4/18

Streaming II

Lec 23
4/23

Search problems, Complexity Theory

§

notes (primary), 8.1 (secondary), slides, webcast

Lec 24
4/25

NP-Completeness

§

notes (primary), 8.2, 8.3 (secondary), webcast

Lec 25
4/30

Coping with NP-completeness

§

9.2, webcast

Lec 26
5/2

Coping with NP-completeness

§

9.2, webcast

Midterm 1
2/14

No lecture on 2/14

§ Up to Djikstra's Algorithm on 2/7

Midterm 2
4/3

No lecture on 4/2

§ Up to 3/19

Final
5/17

7-10pm, makeup 10pm-1am

§ The entire class