Lecture: Tu/Th 9:30 am - 11:00 am

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

## Announcements:

Lecture is at this Zoom Link for the first two weeks!

Week | Date | Lecture | Reading | Section | Assignments |
---|---|---|---|---|---|

1 |
Tu 1/18 |
Introduction, big-O notation, arithmetic webcast |
DPV §0 , §1.1 | ||

Th 1/20 |
Divide-and-Conquer (Part I) webcast |
DPV §2.1 , §2.2 , §2.3 | |||

2 |
Tu 1/25 |
Divide-and-Conquer (Part II) Zoom Link |
DPV §2.4 , §2.5 , §2.6 | ||

Th 1/27 |
Fast Fourier Transform |
DPV §2.6 | |||

3 |
Tu 2/1 |
Decompositions of graphs |
DPV §3 | ||

Th 2/3 |
Paths in graphs (Part I) |
DPV §4.1 , §4.2 , §4.3 , §4.4 | |||

4 |
Tu 2/8 |
Paths in graphs (Part II) |
DPV §4.4 , §4.5 , §4.6 , §4.7 | ||

Th 2/10 |
Greedy Algorithms |
DPV §5 , §5.4 | |||

5 |
Tu 2/15 |
Minimum Spanning Trees |
DPV §5.1 | ||

Th 2/17 |
Union Find |
DPV §5.1.4 | |||

6 |
Tu 2/22 |
Dynamic Programming (Part I) |
DPV §6 | ||

Th 2/24 |
Dynamic Programming (Part II) |
DPV §6 | |||

7 |
Tu 3/1 |
Dynamic Programming (Part III) |
DPV §6 | ||

Th 3/3 |
Linear Programming |
DPV §7.1 | |||

8 |
Tu 3/8 |
Network Flow |
DPV §7.2 | ||

Th 3/10 |
Duality |
DPV §7.4 | |||

9 |
Tu 3/15 |
Zero-Sum Games |
DPV §7.5 | ||

Th 3/17 |
Multiplicative Updates |
notes | |||

10 |
Tu 3/22 |
Spring Break |
|||

Th 3/24 |
Spring Break |
||||

11 |
Tu 3/29 |
Reductions, Bipartite Matching |
DPV §7.3 | ||

Th 3/31 |
Search Problems |
DPV §8.1 | |||

12 |
Tu 4/5 |
Midterm 2 |
|||

Th 4/7 |
NP-Completeness |
DPV §8.2 , §8.3 | |||

13 |
Tu 4/12 |
Coping with NP-completeness |
DPV §9 | ||

Th 4/14 |
Randomized Algorithms |
DPV §1.2 , §1.3 notes | |||

14 |
Tu 4/19 |
Sketching, Streaming |
DPV §1.5 notes | ||

Th 4/21 |
Hashing |
||||

15 |
Tu 4/26 |
Special Topic |
|||

Th 4/28 |
Special Topic |