Schedule, Fall 2021 (everything past the current week is subject to change)

The schedule is continuously updated as the semester progresses.

Recordings of the lectures will be available on Canvas. Also note that the schedule shown below follows the MWF format of Section 1, but the lectures of Section 2 are MW and cover the same material.


Month Week Day Lecture Topic Reading Exercise Assignment
Posted Due
Aug 1 23 Mon Welcome, Course Introduction, Representative Problems (slides)
Sec 2 NameTags 		KT-Ch1 Review CS 220 and prepare for a two hour final exam on the material.
Refresh your python programming skills. Complete the Pre-re-Quiz-ites in Canvas.
Study Python Tutorial, especially dictionaries. 		  E0
25 Wed
27 Fri
2 30 Mon Introduction (contd.)
Orders of magnitude (slides) Line Of Sight algorithm (slides) 		Ch 1.1-3.2
Sep 1 Wed
3 Fri Prerequisites Exam (2 hrs, between 8:00AM and 4:00PM in CSB 110)
3 6 Mon Labor Day, no classes   PA1
8 Wed Survey of common running times (pdf) Heaps and Heapsort (pdf) Ch 6   PA1
10 Fri  
4 13 Mon Graphs (slides) Ch 22  
15 Wed    
17 Fri  
5 20 Mon   WA1 WA1
22 Wed Greedy Algorithms (slides) Ch 16.1-16.3  
24 Fri    
6 27 Mon Divide & Conquer, Master Theorem (slides) Ch 4.1, 4.3, 4.5    
29 Wed Review Heaps Quiz, Graphs Quiz, Greedy Quiz (in Canvas)  
Oct 1 Fri Midterm 1
7 4 Mon More greedy algorithms: Minimum Spanning Trees
Shortest Paths (slides1, slides2) 		Chs 23 24    
6 Wed    
8 Fri Recurrences Quiz    
8 11 Mon More Divide & Conquer: Counting Inversions (slides)
Karatsuba's algorithm (polynomial multiplication) 		PA2 PA2
13 Wed
15 Fri Closest Point Pair (slides) Ch 33.4    
9 18 Mon Dynamic Programming: Recursive substructure, memoization
Weighted Interval Scheduling, Knapsack (slides) 		Ch 15,
KPDP-full.xlsx 		  WA1bis
20 Wed  
22 Fri WA1-bis (60 minute Canvas Quiz)  
10 25 Mon Momory Efficient Knapsack, No-backtrack knapsack KPDP-ME.xlsx     WA1
bis
27 Wed Subset-Sum, Making Change (slides) (Jack’s slides) WA2
29 Fri Shortest Paths revisited: Bellman Ford (slides) Ch 24.1   WA2
Nov 11 1 Mon Matrix Chain Product, OSP (OSP.xlsx) Ch 15.2  
3 Wed Midterm 2 review Quizes on Recurrences, D&C, Dynamic Programming (KP, BF, WIS, etc.)  
5 Fri Midterm 2 PA3 PA3
12 8 Mon Midterm 2 discussion
Dynamic Multi-Threading (DMT) (slides) 		Ch 27  
10 Wed  
12 Fri
13 15 Mon Parallel Scans (Prefix Sums), Reductions, and Fib ScanExample.xlsx wiki WA3
17 Wed  
19 Fri  
Fall Recess, (gobble gobble)
14 29 Mon Reductions (the other kind slides)
SAT⇒3SAT 		Ch 34.1-3   WA3
Dec 1 Wed  
3 Fri DMT Quiz   WA4
15 6 Mon  
8 Wed P, NP, NPC (slides)  
10 Fri Wrap up and recap  
Final Exam CSB 110 Tuesday December 14; arrive 8ᴀᴍ–2ᴘᴍ for a two-hour exam