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

Instructor:

Teaching Assistant:

Meeting Times:

Wednesday, 6:30 - 9:20 pm, EE1 045

CSEP 521 E-mail Announcements

We will periodically send out important information via email to the course email group. To subscribe to the group, you should visit the list home page, http://mailman.cs.washington.edu/mailman/listinfo/csep521 to add yourself, or you can use the email interface to subscribe. Email to csep521-request@cs with the word "help" in the subject will return a message listing all of the email command options. You can also vist the list archives by clicking on the very first URL on the list "home page", or by clicking here. Please note that we will use this group as an announcement list only; if you have a homework question or some other topic that you'd like to discuss with your fellow students, do so on the course message board (described below).

CSEP 521 Message Board

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

Assignments

Please read the grading guidelines. Also note that if you choose to submit your assignment as a soft copy, you should send only a PDF/PS file as an attachment to Roee and make sure that the name of the file you attach clearly indicates your name and the assignment number (this information should also appear in the file submitted).

Assignment 1 due 7pm, January 13, 2007. Solution
Assignment 2 due 7pm, January 27, 2007 Solution
Assignment 3 due 7pm, February 3, 2007 Solution
Assignment 4 due 7pm, February 10, 2007 Solution
Assignment 5 due 7pm, February 17, 2007 Solution, part a; Solution, part b
Assignment 6 due 7pm, February 26, 2007 Solution

Exam due March 7, 2007
Solution

Project

Please read the project description.
This year's projects

Lectures (slides require password)

Lecture 1: Course Introduction, Stable Marriage, Review of basics (Chapters 1-2)
Lecture 2: Graphs, BFS, Connectivity, Topological Sort, DFS (and Articulation points), Greedy Algorithms, including Shortest Paths (Chapter 3, 4.1-- 4.4)
Lecture 3: MST; Divide & Conquer (counting inversions, closest pair of points, integer multiplication) (Sections 4.5-4.7, 5.1--5.5)
Lecture 4: Fast Fourier Transform; dynamic programming(applications in scheduling and computational biology) (Sections 5.6, 6.1-- 6.7)
Lecture 5: Bellman/Ford; theory of network flow network flow applications (Sections 6.8- 6.10, 7.1-- 7.3, 7.5 -- 7.12)
Lecture 6: Finish up network flow, linear programming (Chapter 7 of Dasgupta et al book).
Lecture 7: Finish up linear programming, NP-completeness (part 1, part 2 , part 3 ) (Chapter 8)
Lecture 8: Coping with NP-completeness --branch and bound, local search, approximation algorithms, etc. (part 1, part 2)
Lecture 9: Randomized algorithms (part 1, part 2)
Lecture 10: Student Project Presentations

Textbook

The textbook will be used as a resource for most of the course.

Algorithm Design
Jon Kleinberg and Eva Tardos
Addison Wesley, 2005

Algorithm Resources

These resources may be helpful in your studies.

Grading

Collaboration

You are allowed to collaborate with your classmates on formulating ideas for solving the homework problems. When it comes to writing up solutions, if you wish, you may pair up with one other student on the preparation and submission of a single joint written homework. On the homework you submit, please include a list of all the people that you discussed the problems with. You may not consult written materials other than the course materials in coming up with your solutions. Needless to say, you are expected to maintain the utmost level of academic integrity in the course.


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