CSE 421: Introduction to Algorithms

Autumn, 2017

Paul Beame

MWF 4:30-5:20, EEB 125
Office hours in CSE 668:
Mon 5:20-5:50, Wed 3:30-4:20, 5:20-5:50

Email list:
Class email list: cse421a_au17     [archives]

Please send any e-mail questions about the course to cse421-staff@cs.

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 plus some additional material from later chapters. 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

Grading Scheme (Roughly):

Homework 50%
Midterm 15-20%
Final Exam 30-35%

Course Calendar
Note that there will not be a class on November 22, the Wednesday before Thanksgiving.

Lecture Slides
Reading Assignments
  • Chapters 1 and 2 of Kleinberg and Tardos
  • Chapter 3 of Kleinberg and Tardos
  • Sections 4.1-4.7 of Kleinberg and Tardos
  • Chapter 5 of Kleinberg and Tardos
  • Algebraic Divide and Conquer from Manber's text.
  • Section 13.5 of Kleinberg and Tardos
  • Chapter 6 of Kleinberg and Tardos
  • Sections 7.1-7.3,7.5,7.6,7.11 of Kleinberg and Tardos
  • Chapter 8 of Kleinberg and Tardos

Homeworks [Grading and academic integrity guidelines]:

Homework submission is due via Canvas


  • Midterm exam:
    In Gowen 301 at the regular class time on Friday, 3-Nov-2017. This will be open book and open notes, hard copies only. The coverage includes all topics through divide and conquer. An old sample midterm is available along with sample solutions.
    There will be a review session on Thursday, 2-Nov-2017 at 4:30 pm in MGH 241. Please bring your questions.
  • Final exam:
    In Gowen 301 on Monday, 11-Dec-2017 at 4:30-6:20 pm as shown in the UW exam schedule. This will be open book and open notes, hard copies only. There is an old final exam and a practice final from previous offerings of the course. There are also solutions to the practice final. There will be a review session on Sunday, 10-Dec-2017 at 4:00 pm in our usual classroom, EEB 125. Please bring your questions.

TA Office hours (from October) Room
Isaac Ahn Wed 12:00-12:50 CSE 021
Farzam Ebrahimnejad Tue 11:00-11:50 CSE 021
Jay Garlapati Thu 12:30-1:20 CSE 007
Qisheng Li Mon 2:30-3:20 CSE 007
Sai Nimmagadda Thu 10:30-11:20 CSE 220
Anna Pendleton Wed 2:30-3:20 CSE 007
Peter West Thu 2:00-2:50 CSE 220

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-2017, Paul G. Allen School of Computer Science and Engineering, University of Washington.