###
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:

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