Lecture: Tu/Th 9:00 am - 10:30 am
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)
Jump to current weekAnnouncements:
- Discussion 5 walkthrough is posted!
- Week 6 mini-lecture is posted!
- Homework 5 walkthrough is posted!
Week | Date | Lecture | Reading | Section | Videos | Assignments |
---|---|---|---|---|---|---|
1 |
Tu 1/19 |
Introduction, big-O notation, arithmetic webcast | youtube mirrorPassword: $t*x9h*^
Prof. Chiesa's notes
|
DPV §0 , §1.1 |
|
||
Th 1/21 |
Divide-and-Conquer (Part I) webcast | youtube mirrorPassword: 4xr@=yrr
Prof. Chiesa's notes
|
DPV §2.1 , §2.2 , §2.3 | ||||
2 |
Tu 1/26 |
Divide-and-Conquer (Part II) webcast | youtube mirrorPassword: .6XiwsPg
Prof. Chiesa's notes
|
DPV §2.4 , §2.5 , §2.6 |
|
||
Th 1/28 |
Fast Fourier Transform webcast | youtube mirrorPassword: xswe&CN3
Prof. Chiesa's notes
|
DPV §2.6 | ||||
3 |
Tu 2/2 |
Decompositions of graphs webcast | youtube mirrorPassword: P%4T@dCS
Prof. Chiesa's notes
|
DPV §3 |
|
||
Th 2/4 |
Paths in graphs (Part I) webcast | youtube mirrorPassword: VIY$L&n4
Prof. Chiesa's notes
|
DPV §4.1 , §4.2 , §4.3 , §4.4 | ||||
4 |
Tu 2/9 |
Paths in graphs (Part II) webcast | youtube mirrorPassword: %b5wLL*8
Prof. Demmel's notes
|
DPV §4.4 , §4.5 , §4.6 , §4.7 |
|
||
Th 2/11 |
Greedy Algorithms webcast | youtube mirrorPassword: *q7QQBr*
Prof. Demmel's notes
|
DPV §5 , §5.4 | ||||
5 |
Tu 2/16 |
Minimum spanning trees webcast | youtube mirrorPassword: @AB3?uJ%
Prof. Demmel's notes
|
DPV §5.1 |
|
||
Th 2/18 |
Midterm 1 (9:00am - 11:00am PST) Midterm prepMidterm prep sols |
|||||
6 |
Tu 2/23 |
Huffman encoding and Horn formulas webcast | youtube mirrorPassword: @?YUZ#s8
Prof. Demmel's notes
|
DPV §5.2 , §5.3 |
|
||
Th 2/25 |
Dynamic Programming (Part I) webcast | youtube mirrorPassword: 2?KtSy4G
Prof. Demmel's notes
|
DPV §6 | ||||
7 |
Tu 3/2 |
Dynamic Programming (Part II) |
DPV §6 | |||
Th 3/4 |
Linear Programming |
DPV §7.1 | ||||
8 |
Tu 3/9 |
Network Flow |
DPV §7.2 | |||
Th 3/11 |
Duality |
DPV §7.4 | ||||
9 |
Tu 3/16 |
Midterm 2 (9:00am - 11:00am PST) |
||||
Th 3/18 |
Zero-Sum Games |
DPV §7.5 | ||||
10 |
Tu 3/23 |
Spring Break! |
||||
Th 3/25 |
Spring Break! |
|||||
11 |
Tu 3/30 |
Multiplicative Updates |
notes | |||
Th 4/1 |
Reductions, Bipartite Matching |
DPV §7.3 | ||||
12 |
Tu 4/6 |
Search Problems |
DPV §8.1 | |||
Th 4/8 |
NP-Completeness |
DPV §8.2 , §8.3 | ||||
13 |
Tu 4/13 |
Coping with NP-completeness |
DPV §9 | |||
Th 4/15 |
Randomized Algorithms |
DPV §1.2 , §1.3 | ||||
14 |
Tu 4/20 |
Sketching, Streaming |
DPV §1.5 notes | |||
Th 4/22 |
Lower Bounds |
|||||
15 |
Tu 4/27 |
Hashing |
DPV §1.5 | |||
Th 4/29 |
Interactive Proofs (special topic) |
Final time: Wednesday 5/12, 11:30am - 2:30pm PST