CSCI 358 - Fall 2025

Applied Algorithms

Home | Lectures | Assignments | Handouts | 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
5 Sep C Review; Analyzing Efficiency struct.c
pointers.c
memory1.c 		slides C Reviews in Handouts
9 Sep Meet in the Middle sort.c
variabletypes.c
Makefile
 slides
12 Sep Optimization unsortedlinkedlist.c
sortedlinkedlist.c 		slides
16 Sep External Memory Model smallunsortedlinkedlist.c
 slides Notes from Jeff Erikson
Example Handout
19 Sep Hirshberg's Algorithm board 1
board 2
board 3
 slides [Kleinberg Tardos] p.284
Hirschberg's paper
23 Sep Cost of Operations timetests.c
timetests2.c
branchpredictions.c
latencythroughput.c
 slides

Part 2: Probability and Hashing

Date Lecture Examples Slides Reading
26 Sep Operations Continued slides
30 Sep Intro to Probability slides Probability Tips
3 Oct Mountain Day
7 Oct Filters and Hashing slides Lecture Notes
10 Oct Streaming slides lecture notes
Facebook article
17 Oct Locality-Sensitive Hashing slides book chapter (Ignore shingling and banding)
21 Oct Review CMS: 1 2 3 4 5
Ext. Mem: 1 2 		Practice Midterm
Practice Midterm Solutions
24 Oct Midterm

Part 3: Strings and Trees

Date Lecture Examples Slides Reading
28 Oct Van Emde Boas Trees slides
31 Oct Suffix Arrays Board: 1 2 3 slides Suffix Array Writeup
4 Nov String Compression slides
7 Nov Burrows-Wheeler Transform

Part 4: LP and ILP

Date Lecture Examples Slides Reading
11 Nov Linear Programming Notes from Jeff Erikson
(Only H1-H3)
14 Nov Integer Linear Programming
18 Nov ILP Practice
21 Nov Simplex Algorithm
25 Nov Solving ILPs and Primal-Dual
2 Dec Project Meetings
5 Dec Review