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/21

Lec 18
4/4

Linear Programming

§

7.5

12
Lec 19
4/9

Convex Optimization

§

notes

Lec 20
4/11

Convex Optimization

§

notes

13
Lec 21
4/16

Streaming Algorithms

§

notes

Lec 22
4/18

Streaming

§

notes

14
Lec 23
4/23

Streaming

§

notes

Lec 24
4/25

Search problems, Complexity Theory

§

8.1

15
Lec 25
4/30

NP-Completeness

§

8.2, 8.3

Lec 26
5/2

Coping with NP-completeness

§

9

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

§

7.5

Lec 19
4/9

Convex Optimization

§

notes

Lec 20
4/11

Convex Optimization

§

notes

Lec 21
4/16

Streaming Algorithms

§

notes

Lec 22
4/18

Streaming

§

notes

Lec 23
4/23

Streaming

§

notes

Lec 24
4/25

Search problems, Complexity Theory

§

8.1

Lec 25
4/30

NP-Completeness

§

8.2, 8.3

Lec 26
5/2

Coping with NP-completeness

§

9

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/21

Final
5/17

7-10pm, makeup 10pm-1am

§ The entire class