CS4800: Algorithms and Data

[Home] [Schedule]
The schedule is tentative and subjects to change (e.g. snow days)
Date Topic Reading Problem sets
Jan 9
Introduction, induction
Lecture slides
DPV Chapter 0
Erickson Appendix I
PS0 out
PS0 source
Jan 12
asymptotic order of growth, Karatsuba
Lecture slides
Karatsuba: Erickson 1.8, demo
PS0 due
PS1 out
PS1 source
Jan 16
recursion tree, mergesort
Lecture slides
Erickson Appendix II.1-3
Mergesort: demo
Jan 19
Master theorem, change of variable
Lecture slides
Master theorem: Erickson Appendix II.3
PS1 due
PS2 out
PS2 source
Jan 23
deterministic median
Lecture slides
Erickson 1.7
Jan 26
Random variables, quicksort
Lecture slides
Erickson 9
PS2 due
PS3 out
PS3 source
Jan 30
coin change, dynamic programming
Lecture slides
Erickson 5.1-5.5
Feb 2
log cutter, knapsack
Lecture slides
PS3 due
PS4 out
PS4 source
Feb 5
seam carving, typesetting
Lecture slides
Seam carving: paper
Typesetting: MIT video
Feb 9
typesetting, gerrymander
Lecture slides
Erickson 5.5
PS4 due
PS5 out
PS5 source
Feb 13
Midterm 1
Feb 16
edit distance, greedy algorithms, files on tape
Lecture slides
Erickson 7.1, 7.3
Feb 20
interval scheduling
Lecture slides
Erickson 7.2
Feb 23
Huffman coding
Lecture slides
Erickson 7.4
PS5 due
PS6 out
PS6 source
Feb 27
graph, depth first search, topological sort
Lecture slides
Erickson 19.1-19.5
Mar 2
Minimum spanning trees, generic algorithm
Lecture slides
Erickson 20.1-20.3
PS6 due
PS7 out
PS7 source
Mar 13
No class, snow day
Mar 16
Prim, Kruskal
Lecture slides
Erickson 20.4,20.6
PS7 due
PS8 out
PS8 source
Mar 20
Breadth-first search, shortest paths
Lecture slides
Erickson 21.1-21.4
Demos for BFS, Dijkstra's
Mar 23
Bellman-Ford, all-pairs shortest paths
Lecture slides
Erickson 21.6, Erickson 22
PS8 due
PS9 out
PS9 source
Mar 27
Midterm 2
Mar 30
Network flow, maximum flows and minimum cuts
Lecture slides
Erickson 23.1-23.4
Apr 3
Lecture slides
Erickson 23.6.2
Apr 6
bipartite matching, image segmentation
Lecture slides
Matching: Erickson 24.3
PS9 due
PS10 out
PS10 source
Apr 10
Stable matchings
Lecture slides
Erickson 0.5
Apr 13 Hashing, fingerprinting
Lecture slides
High Speed Hashing for Integers and Strings
PS10 due
Apr 17 Fingerprinting, Bloom filter
Lecture slides