Materials

Midterm 1

2/14

No lecture on 2/14

§ Up to Djikstra's Algorithm on 2/7

Sec 4

Section 4 Solutions

HW 4

Homework 4 Solutions

5 Lec 8

2/19

Greedy Algorithms, MST

Lec 9

2/21

Greedy Algorithms

Sec 5

Section 5 Solutions

HW 5

Homework 5 Solutions

6 Lec 10

2/26

Dynamic Programming

Lec 11

2/28

Dynamic Programming

Sec 6

Section 6 Solutions

HW 6

Homework 6 Solutions

7 Lec 12

3/5

Dynamic Programming

Lec 13

3/7

Dynamic Programming

Sec 7

Section 7 Solutions

HW 7

Homework 7 Solutions

8 Lec 14

3/12

Linear Programming

7.1, webcast, slides

Lec 15

3/14

Linear Programming

7.4, 7.6, webcast, slides

Sec 8

Section 8 Solutions

HW 8

Homework 8 Solutions

9 Lec 16

3/19

Linear Programming

7.2, webcast, slides

Lec 17

3/21

Linear Programming

7.3, webcast, slides

Sec 9

Section 9 Solutions

HW 9

Homework 9 Solutions

10 Spring Break

No Sec

Section Solutions

No HW

Homework Solutions

11 Midterm 2

4/3

No lecture on 4/2

§ Up to 3/19

Lec 18

4/4

Linear Programming

7.5, webcast, slides

Sec 10

Section 10 Solutions

HW 10

Homework 10 Solutions

12 Lec 19

4/9

Multiplicative Weights

Lec 20

4/11

Follow the Regularized Leader

Sec 11

Section 11 Solutions

HW 11

Homework 11 Solutions

13 Lec 21

4/16

Streaming I

Lec 22

4/18

Streaming II

Sec 12

Section 12 Solutions

HW 12

Homework 12 Solutions

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

Sec 13

Section 13 Solutions

HW 13

Homework 13 Solutions

15 Lec 25

4/30

Coping with NP-completeness

Lec 26

5/2

Coping with NP-completeness

Sec 14

Section 14 Solutions

HW 14

Homework 14 Solutions

16 RRR Week

No Sec

Section Solutions

HW 15

Homework 15 Solutions

Lec 1

1/22

Intro, O() notation, Integer multiplication

0, 2.1, webcast, slides

Week 1

Lec 2

1/24

Matrix multiplication, Master theorem

2.2, 2.5, webcast, slides

Week 1

Lec 3

1/29

FFT

2.6, webcast, slides

Week 2

Lec 4

1/31

FFT, Graphs

2.6, 3.1, webcast, slides

Week 2

Lec 5

2/5

DFS, Graph Decomposition

3, webcast, slides

Week 3

Lec 6

2/7

Shortest Paths

4, webcast, slides

Week 3

Lec 7

2/12

Shortest Paths, Bellman-Ford

Week 4

Lec 8

2/19

Greedy Algorithms, MST

Week 5

Lec 9

2/21

Greedy Algorithms

Week 5

Lec 10

2/26

Dynamic Programming

Week 6

Lec 11

2/28

Dynamic Programming

Week 6

Lec 12

3/5

Dynamic Programming

Week 7

Lec 13

3/7

Dynamic Programming

Week 7

Lec 14

3/12

Linear Programming

7.1, webcast, slides

Week 8

Lec 15

3/14

Linear Programming

7.4, 7.6, webcast, slides

Week 8

Lec 16

3/19

Linear Programming

7.2, webcast, slides

Week 9

Lec 17

3/21

Linear Programming

7.3, webcast, slides

Week 9

Lec 18

4/4

Linear Programming

7.5, webcast, slides

Week 11

Lec 19

4/9

Multiplicative Weights

Week 12

Lec 20

4/11

Follow the Regularized Leader

Week 12

Lec 21

4/16

Streaming I

Week 13

Lec 22

4/18

Streaming II

Week 13

Lec 23

4/23

Search problems, Complexity Theory

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

Week 14

Lec 24

4/25

NP-Completeness

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

Week 14

Lec 25

4/30

Coping with NP-completeness

Week 15

Lec 26

5/2

Coping with NP-completeness