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 | Wed,Thu 11-12 or by Appointment | Sieg 416 | 543-5114 |
| TAs: | Ioannis Giotis | giotis@cs | Thu 2-3 | Sieg 226b | |
| Samir Shaunak | samir@cs | Tue 2-3 | Sieg 226b |
Grading: Homework 45-55%, Midterm 15-20%, Final 30-35%, give or take. Extra Credit.
Textbook
Introduction to Algorithms by Jon Kleinberg and Eva Tardos. This is a pre-print available from Professional Copy and Print, 4200 University Way (one block S. of the University Bookstore), for $26.20 plus tax.
In addition, I will borrow a small amount of material from Introduction to Algorithms, Second Edition, by Cormen, Leiserson, Rivest, and Stein which should be available from the University Bookstore. Used copies may be available there or through on-line retailers such as Amazon.com.
Our main textbook is a work in progress and does not have an index, so it is not currently suitable as a reference book. The CLRS text is as good as any to serve as an algorithms and data structures handbook for future use.
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 14 in class.
Final Exam: Monday, March 17, 2:30-4:20 p.m.
Extra Credit Opportunities: Because we are using an unpublished book, we have a great opportunity to give feedback to the authors so they can improve the book. To encourage you in this way, I will give you an extra credit point for each suggestion you make for how the book could be improved. Suggestions could be things like pointing out typos, pointing out places in the text where you think the explanation is unclear (and proposing an alternative explanation), suggesting additions to text or figures that could enhance the presentation, etc.
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.