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.


Part 1: Time and Space

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 External-Memory 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 Mini-Midterm 1 lecture 7
midterm topics
EM 3Sum paper

Part 2: Probability and Hashing

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, Count-Min Sketch, HyperLogLog Counting lecture 10 lecture notes
FB HLL

18 Oct Code Review, Hashing, SIMD Instructions trailingZeroes.c lecture 11

21 Oct Locality-Sensitive 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 Mini-Midterm 2 & Linear Programming Into

Part 3: Linear Programming

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 Mini-Midterm 3

15 Nov No class!

Part 4: Trees and Strings

Date Lecture Examples Slides Reading

18 Nov Burrows-Wheeler Transform

22 Nov Code Review; Suffix Arrays and Suffix Trees

29 Nov Least Common Ancestor

Dec 1 Linear-Time Suffix Tree Construction

Dec 6 Van Emde Boas Trees

Dec 9 Review