CSCI 358 - Fall 2024
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 |
| 6 Sep | Welcome, Some C |
struct.c pointers.c memory1.c |
lecture 1 | Handouts courtesy of Prof. Dan Barowy: C intro Memory Management Passing Pointers |
| 10 Sep | Space for Time: Meet in the Middle |
sort.c variabletypes.c Makefile |
lecture 2 | |
| 13 Sep | Optimization and Efficiency |
timetests.c timetests2.c branchpredictions.c |
lecture 3 | |
| 17 Sep | Optimization Contd., The External-Memory Model | latencythroughput.c sortedlinkedlist.c unsortedlinkedlist.c smallunsortedlinkedlist.c | lecture 4 |
Lecture notes from Jeff Erikson Example Handout |
| 20 Sep | Time from Space: Hirshberg's Algorithm | lecture 5 |
[Kleinberg Tardos] p.284 Hirschberg's paper |
|
| 24 Sep | External Memory contd., Code Review | lecture 6 | ||
| 27 Sep | Topics for Assignment 1, intro Probability |
lecture 7 Assign. 1 slides |
||
| Date | Lecture | Examples | Slides | Reading |
| 1 Oct | Filters | lecture 8 | Lecture Notes | |
| 4 Oct | Probability and Hashing | lecture 9 | ||
| 8 Oct | Streaming, Count-Min Sketch, HyperLogLog Counting | lecture 10 |
lecture notes FB HLL |
|
| 11 Oct | Mountain Day | |||
| 18 Oct | Locality-Sensitive Hashing: Minhash | lecture 11 | book chapter (Ignore shingling and banding) | |
| 22 Oct | Code Review |
trailingZeroes.c simdtests512.c |
lecture 12 | |
| 25 Oct | SIMD Instructions, Code review | simdtests512.c | lecture 13 | Some SIMD Lecture Notes |
| Date | Lecture | Examples | Slides | Reading |
| 29 Oct | Intro to Linear Programming | lecture 14 |
notes (Only H1-H3) |
|
| 1 Nov | LP Contd. and Simplex |
dietSol.lp walnutOrchard.lp |
lecture 15 | glpk manual (Appendix C) |
| 5 Nov | Integer Linear Programming |
middleSchools.lp dietSolInteger.lp twotowers.lp |
lecture 16 | |
| 8 Nov | Integer Linear Programming Practice | lecture 17 | ||
| 12 Nov | More Integer Linear Programming Practice |
grocery-choice.lp board 1 board 2 |
lecture 18 | |
| 15 Nov | Project Discussion | |||
| Date | Lecture | Examples | Slides | Reading |
| 19 Nov | Burrows-Wheeler Transform | lecture 19 | ||
| 22 Nov | Burrows-Wheeler, Suffix Arrays | lecture 20 | SAIS suffix array construction | |
| 26 Nov | Van Emde Boas Trees | lecture 21 | ||
| Dec 3 | Project Meetings | |||
| Dec 6 | Student Presentations | |||
