CSE 421: Introduction to Algorithms, Autumn 2012
 CSE Home CSE 421 Home About Us Search Contact Info

 Email Archive Homework Assignments Dropbox Homework 1 Homework 2 Homework 3 Homework 4 Homework 5 Homework 6 Homework 7 Homework 8 Reading Assignments Chapter 1 Chapter 2 Chapter 3 Chapter 4, Sections 4.1-4.7 Chapter 5, Section 13.5 Algebraic Divide and Conquer Section 13.5 Chapter 6 Sections 7.1-7.3, 7.5, 7.6, 7.11 Chapter 8 Section 11.3 Lecture Notes Stable Matching Overview Graph Traversal Greedy Algorithms Divide and Conquer Dynamic Programming Flow P, NP, and NP-completeness Dealing with NP-completeness Backtracking for SAT solving Multiplicate Weights Update Method Administrative Course Calendar Grading Guidelines Midterm Topics Sample Midterm Sample Midterm Solutions Final Exam Topics Useful Links SB Algorithm Repository

MWF 1:30-2:20    MGH 241

Office Hours Location Phone
Instructor: Paul Beame   beame@cs
 Mondays 2:20-3:00 Wednesdays 3:00-3:50 and by appointment
CSE 668 543-5114
TAs: Priya Rao Chagaleti cse421-staff@cs
 Tuesdays 12:30-1:20 Thursdays 11:30-12:20
 CSE 216 CSE 218
Dillon Eng cse421-staff@cs
 Tuesdays 1:30-2:20 Thursdays 2:00-2:50
 CSE 218 CSE 220

Grading: Homework 45-55%, midterm 15-20%, final 30-35%, give or take. Extra Credit.

Textbook

• Algorithm Design by Jon Kleinberg and Eva Tardos, Addison-Wesley, 2006.

We will cover almost all of chapters 1-8 of the Kleinberg/Tardos text. In addition, I will borrow a small amount of material on divide and conquer algorithms from Introduction to Algorithms: A Creative Approach, by Udi Manber, Addison-Wesley 1989. I will hand out extra material for this.

Another handy reference is Steven Skiena's Stonybrook Algorithm Repository which is also listed in the Useful Links section on the left column of this page.

Midterm Exam: Friday, November 2 in class. This will be open book (hard copies only) and open notes. Topics for the midterm include material up to the end of dynamic programming. There will be a review session Thursday Nov 1 at 4:30, EEB 045. Old Sample Midterm Solutions to Sample Midterm

Final Exam: Monday, December 10, 2:30-4:20 p.m. This will be open book and open notes. Final Exam Topics There will be a review session on Sunday December 9, 4:00 pm in EEB 037. Old Final Exam Sample from Practice Final Solutions to Sample Practice Final

Suggestions or Comments? You can send comments to the instructor and TAs via the e-mail list "cse421-staff at cs"

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: either CSE 312 or CSE 322; either CSE 326 or CSE 332.

Portions of the CSE 421 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 421 Web: © 1993-2012, Department of Computer Science and Engineering, University of Washington.