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	Edmonds-Karp	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