cs473: ALGORITHMS (FALL 2020)

Below is the calendar for the class (where italicized descriptions are tentative, and topics with question marks (?) may-or-may-not be covered). This includes the lecture topic, the associated suggested reading, lecture recordings, and occasionally a .pdf file of the lecture slides. The psets and pset-schedule are also below.

# Date   Topic Reading psets Video
1 08-26 W Logistics, Motivation and Goals Erickson §1.9   .mp4
  08-27 R     pset0.tex/.pdf out.  
2 08-28 F Divide and Conquer     .mp4
             
3 09-02 W Dynamic Programming (Sequences) Erickson §3   .mp4 .pdf
  09-03 R     pset0 due (solutions).
pset1.tex/.pdf out.
 
4 09-04 F Dynamic Programming (Trees) Erickson §3   .mp4 .pdf
             
5 09-09 W Dynamic Programming (Shortest Paths) Erickson §8, §9; KT §6.8-6.10   .mp4 .pdf
  09-10 R     pset1 due (solutions).
pset2.tex/.pdf out.
 
6 09-11 F Dynamic Programming (Space saving) Erickson §D.1, wikipedia on LIS   .mp4 .pdf
             
7 09-16 W  Randomized Algorithms  Erickson DC §1   .mp4
  09-17 R     pset2 due (solutions).
pset3.tex/.pdf out.
 
8 09-18 F  Randomized Algorithms Erickson DC §4; Har-Peled §10; Harvey §2, §3   .mp4
             
9 09-23 W  Randomized Algorithms (Hashing) Erickson §Z.5; Vadhan §3.5;   .mp4.pdf
  09-24 R     pset3 due (solutions).
pset4.tex/.pdf out.
 
10 09-25 F  Randomized Algorithms (Fingerprinting)     .mp4, .pdf
             
11 09-30 W  Randomized Algorithms (Freivalds etc)     .mp4,  .pdf
  10-01 R     pset4 due (solutions).  
  10-02 F  No video      
             
12 10-07 W Network Flow (Introduction) Erickson §10.0-10.2,10.5; KT §7.0-7.2    pdf
  10-08 R exam1: 6:30-9:30pm (solutions)      
13 10-09 F Network Flow (Algorithms) Erickson §10.3-10.4; KT §7.1-7.2 pset5 .tex/.pdf out  pdf
             
14 10-14 W Network Flow (Algorithms) Erickson §10.6-10.7    pdf
15 10-16 F Network Flow (Applications) Erickson §11.3; KT §7.5 pset6 .tex/.pdf out pdf 
             
16 10-21 W Network Flow (Applications) Erickson §10.511.1-11.2,11.6G.1; KT §7.6,7.12    pdf
  10-22 R     pset5 due (solutions).  
17 10-23 F Linear  Programming (Intro) Erickson §H.1-H.3; Har-Peled §21.5.3   pdf
             
18 10-28 W Linear Programming (Simplex) Erickson §H.4-H.6; Har-Peled §21.5.3   pdf
          pset7 .tex/.pdf out  
  10-29 R     pset6 due (solutions).  
19 10-30 F Linear Programming (Duality) Erickson §H.4-H.6; Chekuri (pdf)   pdf
             
20 11-04 W Reductions     pdf
    R     pset7 due (solutions)
pset8.tex/.pdf out.
 
  11-06 F NP Completeness Erickson §12.1-12.12   pdf
             
21 11-11 W NP Completeness Erickson §12.1-12.12   pdf
    R    
pset8 due (solutions)
 
22 11-13 F        
             
  11-15 S exam2 review session: 7.00-8.30pm      
  11-16 M exam2: 6:30-9:30pm (solutions)      
23 11-18 W     pset9 .tex/.pdf out  
24 11-20 F Heuristics and Approx Algrotihms Erickson notes   pdf
             
  11-25 W break      
  11-27 F break      
             
25 12-02 W Approximation Algrotihms
Erickson notes
  pdf
  12-03 R     pset9 due (solutions)  
26 12-04 F Approximation Algrotihms
Erickson notes
  pdf
             
27 12-09 W     Optional, not for submission
Fall 2019: pset10 (solutions)
Fall 2019: pset11
Fall 2016: hw10
Fall 2016: hw11
 
             
  12-??   final