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 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 | |
| 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 |
simdexamples.c autosimd.c |
lecture 13 | SIMD Lecture Notes |
| 28 Oct | Mini-Midterm 2: Robin hood hashing | lecture 14 | ||
| Date | Lecture | Examples | Slides | Reading |
| 1 Nov | Intro to Linear Programming | lecture 15 |
notes (Only H1-H3) |
|
| 4 Nov | Simplex Method & LP solvers |
dietSol.lp walnutOrchard.lp |
lecture 16 | glpk manual (Appendix C) |
| 8 Nov | Integer Linear Programming and Applications | middleschools.lp | lecture 17 | |
| 11 Nov | ILP and MIP Continued |
dietSolChoose.lp dietSolChoose.out |
lecture 18 | |
| 15 Nov | No class! | |||
| Date | Lecture | Examples | Slides | Reading |
| 18 Nov | Burrows-Wheeler Transform | lecture 19 | ||
| 22 Nov | Burrows-Wheeler Transform Cont. | lecture 20 | ||
| 29 Nov | Linear-Time Suffix Tree Construction 1 | lecture 20 | lecture notes | |
| Dec 1 | Linear-Time Suffix Tree Construction 2 | lecture 22 | Stanford slides | |
| Dec 6 | van Emde Boas Trees | Board photos: 1: P to LMS to BlockAssgn 2: Recursive Call 3: Induced Sort |
lecture 23 | |
| Dec 9 | Review | lecture 24 | ||
