CSE 521 - Design and Analysis of Algorithms, Spring 2009

Old final: Look at questions 1 and 4 on this exam for some more examples of final questions.

Course Info

Lectures:
TTh 12:00 - 1:20 PM, CSE 203

Course Staff:
Instructor: James Lee
TA: Thach Nguyen

Office Hours:

James: Tuesday and Thursday, by appointment (just shoot me an email)
Thach: Wed 330-530 in CSE 218

If you need an appointment and can't make it to the scheduled office hours, please email us, and we will set up some other time.

Slides and lecture notes

Lecture 1: Intro, nearest-neighbor search, and dimensionality of data [pps (PPT'07), ppt (PPT'03), PDF]
Lecture 2-3: Shortest paths (notes) and Fibonacci heaps (notes, slides). Notes on amortized analysis and potential functions.
Lecture 4: Max-flow/min-cut (slides)
Lecture 5: Network flow applications (slides)
Lecture 6: Randomized quicksort (notes), Randomized min-cuts (notes, experimental study)
Lecture 7-8: Linear programming (notes, DPV book)
Lecture 9: Strong duality and the simplex algorithm (notes)
Lecture 10-11: NP-completeness and intractability (intractability, reductions, and NP-completeness)
**midterm** (out: Thursday, May 14, due: May 21)
Lectures 12-13: Approximation algortihms (Reading: Chapter 11 of KT)
Lecture 14: Sparsest Cut (related notes; see also Bourgain's embedding)
Lectures 15-16: Spectral partitioning (notes1, notes2, Cheeger's inequality)
Lecture 17: Hashing (notes, power of 2 choices)
Lecture 18: Cuckoo hashing (video, notes, paper)
Lecture 19: Concentration of random sums (notes)
Lecture 20: Dimension reduction in Euclidean spaces (Lemma 7.1 here)

Textbook

We will be using the book, Algorithm Design (Addison Wesley, 2005), by Jon Kleinberg and Eva Tardos.

Grading

The rough grading split will be as follows:

5 problem sets (5*10%) (roughly bi-weekly)
1 take-home midterm (15-20%)
1 in-class (open book) final (30-35%)

Problem Sets

Problem set	Due	PDF	Solutions
Homework 1	Apr 9	ps1	sol1
Homework 2	Apr 23	ps2	sol2
Homework 3	May 7	ps3	sol3
Midterm	May 21	midterm	solutions
Homework 4	June 4	ps4
Homework 5

We have a preference for typed solutions. If that is not possible, please be sure to write very clearly.

Class Mailing List

The mailing list (cse521@cs.washington.edu) is used to communicate important information that is relevant to all the students. Make sure that you are registered to it, by visiting this page.

The mailing list is also a very useful tool for collaboration and interaction between students. You are encouraged to post questions, thoughts, and ideas, that you believe would interest your fellow students.

Messages to the mailing list are stored in the archive.

Academic Integrity and Collaboration

You are allowed to collaborate with your classmates to the extent of formulating ideas. When it comes to writing up solutions, you should do this by yourself. No collaboration on the actual writing of homework solutions is allowed. On the homework you submit, please include a list of all the people that you discussed the problems with. Needless to say, you are expected to maintain the utmost level of academic integrity in the course.


	Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to roee]