CSE logo University of Washington Computer Science & Engineering
 CSEP 521 - Applied Algorithms - Autumn 2009
  CSE Home   About Us    Search    Contact Info 

Instructor:

Teaching Assistant:

Meeting Times:

Mondays, 6:30 - 9:20 pm, EEB 037
There will be no class on October 26. This class will be made up on December 14.

CSEP 521 E-mail Announcements

We will periodically send out important information via email to the course email group. All registered students are on the e-mail list with their UWNet ID e-mail box. If you want your messages forwared to your private e-mail address then go to MyUW to forward your e-mail. You may look at the mailing list archive to find past e-mails. If you have a homework question or some other topic that you'd like to discuss with your fellow students, the instructor, or TA, do so on the course discussion board (described below).

CSEP 521 Discussion Board

Use the discussion board to ask questions and consult with each other about the homework and anything else related to class.

Assignments

Assignments are due each Monday at the beginning of class (late assignments not accepted without prior approval).

Assignment 1 due 10/12. Chapter 1, Exercises 1, 2, 4, 6 (reduce to stable matching problem). Chapter 2 Exercises 3, 4. Solutions to HW1
Assignment 2 due 10/19. Chapter 3, Excercises 4, 9 (think of using breadth-first search), 11 (reduce to a reachability problem). Chapter 4, Excersise 4 (think greedy and show why it works).Solutions to HW2
Assignment 3 due 11/2. Chapter 4, Exersises 13, 19, 24. Chapter 5, Exercises 3, 5. Solutions to HW3
Assignment 4 due 11/9. Chapter 6, Exercises 1, 6, 20. Solutions to HW4
Assignment 5 due 11/16. Chapter 6, Exercise 19. Chapter 7, Exercises 19, 23.Solutions to HW5
Assignment 6 due 11/23. Chapter 7, Excercise 45. Chapter 8, Exercises 3, 26. Solutions to HW6
Assignment 7 due 12/7. From Chapter 7 of Dasgupta, Papadimitriou, and Vazirani. Problem 7.5.

Project

Please read the project description. There are three components to the project.
  1. The one page project proposal is due in class on Monday, November 2, 2009.
  2. The final report is due Tuesday, December 8, 2009. Final reports must be uploaded to the Project Discussion Board by 11:30 pm, Tuesday, December 8, 2009.
  3. All students are required to read and comment on at least 3 other reports by 11:30 pm, Wednesday December 16, 2009. All comments should be respectful and add some value to the particular project report that is being commented on.

Reading

9/28/09 - 10/04/09: Chapters 1 and 2.
10/5/09 - 10/11/09: Chapter 3 and Chapter 4 (4.1-4.4).
10/12/09 - 10/19/09: Chapter 4 (4.5-4.7) and Chapter 5 (5.1-5.5).
10/28/09 - 11/01/09: Chapter 5 (5.6) and Chapter 6 (6.1-6.7).
11/2/09 - 11/8/09: Chapter 6 (6.8-6.10) and Chapter 7 (7.1-7.3, 7.5-7.12)
11/8/09 - 11/15/09: Chapter 8
11/16/09 - 11/22/09: Chapter 12
11/23/09 - 11/30/09: Chapter 11 (11.6), Chapter 7 from Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
11/30/09 - 12/7/09: Chapter 13 (13.1-13.6, 13.9-13.10)

Lectures

Lecture notes are provided by the publisher.

Lecture 1. 10/5/09. Intro Stable Matching Analysis
Lecture 2. 10/12/09. Graphs, Greedy Algorithms
Lecture 3. 10/19/09. Minimum Spanning Tree, Divide and Conquer, Integer and Matrix Multiplication
Lecture 4. 11/2/09. Polynomial evaluation, interpolation, and multiplication and the FFT (see last pages of the lecture), Dynamic Programming
Lecture 5. 11/9/09. Bellman-Ford Shortest Paths , Network Flow Theory, Network Flow Applications
Lecture 6. 11/16/09. Polynomial Time Reductions, NP-Completeness, More NP-Complete Problems
Lecture 7. 11/23/09. Local Search, Traveling Salesman
Lecture 8. 11/30/09. Linear Programming
Lecture 9. 12/7/09. Randomized Algorithms
Lecture 10. 12/14/09. Dictionary Coding for Lossless Compression, PQ-trees for the Contiguous Ordering Problem

Textbook

Algorithm Design by Jon Kleinberg and Eva Tardos
Pearson/ Addison Wesley, 2006
Textbook web page

Algorithm Resources

These resources may be helpful in your studies.

Grading

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