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
patterns:
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)
Some slides:
Stable matching
Analysis intro
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)
Schedule:
1/19 Introductory examples, Fibonacci numbers
1/21 Stable matching
Other notes:
First-day logistics
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.
Universal hashing.
Crosby-Wallach work on DOS attacks against hashing.
Cuckoo hashing.
Cuckoo hashing for undergraduates.
On splay trees by their inventor.
Algorithm applets:
DFS,
BFS,
Several graph algorithms
Union-find
Union-find
Splay trees
Skip lists