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

Greedy Algorithms, MST

Midterm 1
2/14

No lecture on 2/14

§ Up to Djikstra's Algorithm on 2/7

5
Lec 8
2/19

Greedy Algorithms, Huffman

§

5

Lec 9
2/21

Dynamic Programming

§

6

6
Lec 10
2/26

Dynamic Programming

§

6

Lec 11
2/28

Dynamic Programming

§

6

7
Lec 12
3/5

Dynamic Programming

§

6

Lec 13
3/7

Linear Programming

§

7.1

8
Lec 14
3/12

Linear Programming

§

7.4, 7.6

Lec 15
3/14

Linear Programming

§

7.2

9
Lec 16
3/19

Linear Programming

§

7.3

Lec 17
3/21

Linear Programming

§

7.5

10
Spring Break
Spring Break
11
Midterm 2
4/3

No lecture on 4/2

§ Up to 3/21

Lec 18
4/4

Convex Optimization

§

notes

12
Lec 19
4/9

Convex Optimization

§

notes

Lec 20
4/11

Streaming Algorithms

§

notes

13
Lec 21
4/16

Streaming

§

notes

Lec 22
4/18

Streaming

§

notes

14
Lec 23
4/23

Search problems, Complexity Theory

§

8.1

Lec 24
4/25

NP-Completeness

§

8.2, 8.3

15
Lec 25
4/30

Coping with NP-completeness

§

9

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

Greedy Algorithms, MST

Lec 8
2/19

Greedy Algorithms, Huffman

§

5

Lec 9
2/21

Dynamic Programming

§

6

Lec 10
2/26

Dynamic Programming

§

6

Lec 11
2/28

Dynamic Programming

§

6

Lec 12
3/5

Dynamic Programming

§

6

Lec 13
3/7

Linear Programming

§

7.1

Lec 14
3/12

Linear Programming

§

7.4, 7.6

Lec 15
3/14

Linear Programming

§

7.2

Lec 16
3/19

Linear Programming

§

7.3

Lec 17
3/21

Linear Programming

§

7.5

Lec 18
4/4

Convex Optimization

§

notes

Lec 19
4/9

Convex Optimization

§

notes

Lec 20
4/11

Streaming Algorithms

§

notes

Lec 21
4/16

Streaming

§

notes

Lec 22
4/18

Streaming

§

notes

Lec 23
4/23

Search problems, Complexity Theory

§

8.1

Lec 24
4/25

NP-Completeness

§

8.2, 8.3

Lec 25
4/30

Coping with NP-completeness

§

9

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