The Steam Powered Turing Machine University of Washington Department of Computer Science & Engineering
 CSE 421: Introduction to Algorithms, Spring 2016
  CSE Home   CSE 421 Home  About Us    Search    Contact Info 

Homework Assignments
  Assignment 1
  Assignment 2
  Assignment 3
  Assignment 4
  Assignment 5
  Assignment 6
  Assignment 7
  Assignment 8
Reading Assignments
  Chapter 1
  Chapter 2
  Chapter 3
  Chapter 4, Sections 4.1-4.7
  Chapter 5
  Algebraic Divide and Conquer
  Chapter 13.5
  Chapter 6
  Sections 7.1-7.3,7.5-7.6,7.11
  Chapter 8
Lecture Notes
  Stable Matching
  Graph Traversal
  Greedy Algorithms
  Divide and Conquer
  Dynamic Programming
  Network Flow
  Applications of Network Flow
  P, NP, NP-completeness
  Dealing with NP-completeness
  Backtracking for SAT solving
  Course Calendar
  Grading Guidelines
  Midterm Topics
  Final Exam Topics
Useful Links
  SB Algorithm Repository
MWF 2:30-3:20    MGH 241

NOTE: May 20, class is in THO 325

Office Hours Location Phone
Instructor: Paul Beame   beame@cs  
MWF 3:20-3:50
Wednesdays 10:00-10:50
and by appointment
CSE 668 543-5114
TAs: Xin Yang cse421-staff@cs
Tuesdays 2:30-3:20
Thursdays 11:00-11:50
CSE 218
CSE 218
Kuikui Liu cse421-staff@cs Thursdays 1:30-2:20 CSE 021

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

Homework: There will be 8 roughly weekly homework assignments. Please read the grading guidelines to help you understand what is expected on your homework.


  • 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, May 6, in class. This will be open book and open notes (hard copies only). The following is a list topics for the midterm. There will be a review session in room CSE 403 on Thursday, May 5 at 4:30-6:00 pm. Also, there is a Sample Old Midterm Solutions to Sample Midterm.

Final Exam: Tuesday, June 7, 2:30-4:20 p.m. This will be open book and open notes, hard copy only. Here is a list of topics for the final. There will be a review session Monday, June 6, 4:30-6 in CSE 403. There are an old final exam and a practice final from previous offerings of the course. Solutions to the 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: CSE 312; 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-2016, Department of Computer Science and Engineering, University of Washington.