CSCI 358  Fall 2021
Applied Algorithms
Home  Lectures  Assignments  Handouts  Leaderboard  CS@Williams
Lecture Notes and Examples
Links to lecture slides and files will be available after class on the date shown. The schedule may change as the semester progresses.
Date  Lecture  Examples  Slides  Reading 
9 Sep  Welcome, Intro to Optimization  struct.c pointers.c sort.c memory1.c  lecture 1  Handouts courtesy of Prof. Dan Barowy: C intro Memory Management Passing Pointers 
13 Sep  Optimization and Efficiency  variabletypes.c Makefile latencythroughput1.c latencythroughput2.c timetests.c  lecture 2  
16 Sep  Space for Time: Meet in the Middle  timetests2.c branchpredictions.c cachemisses.c  lecture 3  
20 Sep  Optimization Contd. & The ExternalMemory Model  lecture 4 
Lecture notes from Jeff Erikson Example Handout 

23 Sep  Time from Space: Hirshberg's Algorithm  lecture 5 
[Kleinberg Tardos] p.284 Hirschberg's paper 

27 Sep  External Memory contd., Code Review  lecture 6  
30 Sep  Topics for MiniMidterm 1 
lecture 7 midterm topics 
EM 3Sum paper  
Date  Lecture  Examples  Slides  Reading 
4 Oct  Probability and Hashing 
lecture 8 

7 Oct  Bloom Filters and Cuckoo Filters 
hash example code 
lecture 9 
lecture notes hashing video 
14 Oct  Streaming, CountMin Sketch, HyperLogLog Counting  lecture 10 
lecture notes FB HLL 

18 Oct  Code Review, Hashing, SIMD Instructions  trailingZeroes.c  lecture 11  
21 Oct  LocalitySensitive Hashing: Minhash  lecture 12  book chapter (Ignore shingling and banding)  
25 Oct  LSH Optimizations, SIMD Applications, Code review  SIMD Lecture Notes  
28 Oct  Topics for MiniMidterm 2 & Linear Programming Into  
Date  Lecture  Examples  Slides  Reading 
1 Nov  Using Linear Programming  
4 Nov  Simplex Method & LP solvers  
8 Nov  Integer Linear Programming and Applications  
11 Nov  Topics for MiniMidterm 3  
15 Nov  No class!  
Date  Lecture  Examples  Slides  Reading 
18 Nov  BurrowsWheeler Transform  
22 Nov  Code Review; Suffix Arrays and Suffix Trees  
29 Nov  Least Common Ancestor  
Dec 1  LinearTime Suffix Tree Construction  
Dec 6  Van Emde Boas Trees  
Dec 9  Review  