Textbook: Algorithm Design by Jon Kleinberg and Éva Tardos
Syllabus in postscript and pdf.
Prerequisite course: CSE310.
Homework schedule: (to be filled in)
Homework 1 due 1/26
Homework 2 due 2/2
Homework 3 due 2/11
Homework 4 due 2/18
Homework 5 due 2/25
Homework 6 due 3/25
Homework 7 due 4/13
Homework 8 due 4/29
A few more of the locally-foldable, but globally nonfoldable 2 by n
SEWN, SWEWN, SWEWES, SWESWN, SSESWN, SENWNS.
More on implementation questions:
Directory with homework-related code
Naming scheme for the implementation questions: XXXXXXXXX-HYY-QZZ.py
(X... : the 9-digit ASU ID, YY: the assignment number, ZZ: the question number)
Graph algorithms review
Greedy algorithms (incl. Dijkstra) Minimum spanning trees
Divide and conquer Fast Fourier transform Dynamic programming
Max flow & min cut Max flow applications
NP-completeness NP-completeness reductions Universal hashing (and more)
1/19 Introductory examples, Fibonacci numbers
1/21 Stable matching
Graph representation and traversal
by Jeff Erickson.
Minimum spanning trees by Jeff Erickson.
Single source shortest paths by Jeff Erickson.
Notes on solving recurrences by Jeff Erickson.
Burrows-Wheeler transform and compression.
Crosby-Wallach work on DOS attacks against hashing.
Cuckoo hashing for undergraduates.
On splay trees by their inventor.
Several graph algorithms
Splay trees Skip lists