CSE 450/598 Design and Analysis of Algorithms

Arizona State University, Spring 2010
TuTh 10:30-11:45 BYAC 270

Instructor: Goran Konjevod, BY 450; Office hours: TuTh 1:30--3:00

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:

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)

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
Splay trees Skip lists