Catalog Description: Techniques for design of efficient algorithms. Methods for showing lower bounds on computational complexity. Particular algorithms for sorting, searching, set manipulation, arithmetic, graph problems, pattern matching. Prerequisite: CSE 322; CSE 326.
| Office Hours | Location | Phone | |||
| Instructor: | Paul Beame | beame@cs | M 2:20-2:50, W 11:00-12:00, or by appointment |
CSE 668 | 543-5114 |
| TAs: | Yiannis Giotis | giotis@cs | W 3:30-4:20 | CSE 218 | |
| Th 2:00-2:50 | CSE 216 | ||||
| Peter-Michael Osera | psosera@cs | Th 3:30-4:20 | CSE 216 |
Grading: Homework 45-55%, Midterm 15-20%, Final 30-35%, give or take. Extra Credit.
Textbook
Algorithm Design by Jon Kleinberg and Eva Tardos. This is a pre-print of a text soon to be published by Addison-Wesley and is available from Professional Copy and Print, 4200 University Way (one block S. of the University Bookstore).
We will cover almost all of Chapters 1-8 of the Kleinberg/Tardos text. In addition, I will borrow a small amount of material from Introduction to Algorithms: A Creative Approach , by Udi Manber for which I will give handouts.
Course Web Page: All handouts and a log of all mail sent to the class mailing list will also be available on the course web at:
http://www.cs.washington.edu/421
Mailing List: There is a class mailing list, cse421@cs.washington.edu. Instructions for subscribing to the list can be found on the course web. We will use this list for announcements of general interest to the class. Students should also feel free to use it to ask questions, post information, or initiate discussions of general interest to the class. Questions or comments that are not of general interest should instead be directed to the TAs or instructor at the addresses above.
Midterm Exam: Friday, February 11 in class.
Final Exam: Monday, March 14, 2:30-4:20 p.m.
Homework There will be weekly homework sets, generally due on Fridays. Homework should be handed in at the beginning of lecture on the day it is due. Late homeworks will not receive credit. (If a genuine emergency situation prevents you from handing in an assignment on time, come talk to one of us and we can work something out. Similarly, if you can anticipate an extraordinary or unusual circumstance that will necessitate an extension, please talk to us ahead of time.)
Academic Integrity You are expected to maintain the highest level of academic integrity in the course. Any violation of the code of academic integrity will be penalized severely. You are allowed to collaborate on the homework to the extent of formulating ideas as a group. However, you must write up the solutions to each problem set completely on your own. You must also list the names of everyone that you discussed the problem set with.
Disability Accommodations If you would like to request academic accommodations due to a disability, please contact Disabled Student Service, 448 Schmitz, 543-8924 (V/TDD). If you already have a letter from Disable Student Services indicating that you have a disability that requires academic accommodations, please let the instructor know so we can discuss the appropriate accommodations.