CSE 421: Introduction to Algorithms

Winter, 2021

Paul Beame

Lectures
MWF 1:30-2:20. Zoom link
Office Hours: Zoom link
MWF immediately after class until 2:45 + Wednesdays 4:00-4:50

This course introduces the basic techniques for the design and analysis of algorithms. It is not only about ways to find efficient methods to solve problems, but also about ways to prove the correctness and efficiency properties of these methods.

Textbook:
Algorithm Design by Jon Kleinberg and Eva Tardos, Addison-Wesley, 2006. (The International Edition is the same in paperback.)

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 make extra material available for this.

Another handy reference is Steven Skiena's Stonybrook Algorithm Repository

Grading Scheme (Roughly):

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

Homework assignments will be weekly. It will be useful to start on them early in order to reduce the amount of concentrated time you need to spend on them. You may discuss solutions to the homework problems with your classmates, but you must write all solutions by yourself and indicate all others with whom you have discussed solutions.

You are not allowed to search for solutions to problems on the internet or other sources outside of those given in class, the textbook, and the course web, or share your solutions through such means.

Both the Midterm and Final Exam will be take-home tests.

Email list:
Class email list: cse421a_wi21     [archives]

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

Discussion board:
We will use the Ed discussion board for this class. You will need to sign up by accepting the invitation. Use this board to discuss the content of the course. That includes everything except the solutions to current homework or anything about current exams. Feel free to discuss any confusion over topics discussed in class. It is also acceptable to ask for clarifications about the statement of homework problems, but not about their solutions.

Course Calendar

Lecture Slides
Reading Assignments
  • Chapters 1 and 2 of Kleinberg and Tardos
  • Chapter 3 of Kleinberg and Tardos
  • Chapter 4 of Kleinberg and Tardos
  • Chapter 5 of Kleinberg and Tardos
  • Notes from Manber's Algorithms text
  • Section 13.5 of Kleinberg and Tardos
  • Chapter 6 of Kleinberg and Tardos
  • Chapter 7 of Kleinberg and Tardos
  • Chapter 8 of Kleinberg and Tardos

TA Office hours Zoom
Yonkyu Song Mondays 4:00-4:50 Zoom link
Skyler Hallinan Tuesdays 2:00-2:50 Zoom link
Jenna Yee Wednesdays 11:00-11:50 Zoom link
Liangyu Zhao Wednesdays 3:00-3:50 Zoom link
Anny Kong Thursdays 11:00-11:50 Zoom link
Jason Waataja Thursdays 1:00-1:50 Zoom link
Siddharth Iyer Thursdays 2:30-3:20 Zoom link

Homeworks [Grading & academic integrity guidelines]:

Homework submission is due via Canvas/Gradescope

Exams:

  • Midterm exam:
    As discussed on the first day of class this will be a take-home exam. The midterm exam is designed to be do-able in roughly an hour and certainly substantially less than two hours time. You will have 24 hours for the exam. Your solutions must be hand-written and scanned/photographed for submission through Gradescope. No type-set solutions will be allowed. The exam will be released on Thursday, February 11 at 6:00 p.m. and have a hard submission deadline of Friday, February 12 at 6:00 pm.

    For the midterm, absolutely no collaboration is allowed and no access is allowed to any resources other than the following: this quarter's 421 course slides and videos, the Kleinberg-Tardos textbook, your homework and homework solutions (posted under Pages on the 421 Canvas website).

    If you have any questions during the midterm exam, you should send them to the
    cse421-staff@cs.uw.edu mailing list.
    (Access to the discussion board is forbidden during this time.)

    Any corrections or updates during the final will be communicated through the course mailing list.

    The coverage for the midterm includes all topics through divide and conquer. An old sample midterm is available along with sample solutions. There will be a review session on Wednesday, February 10 beginning at 5:00 p.m. using the following Zoom link.

  • Final exam:
    As discussed on the first day of class this will be a take-home exam. The final exam is designed to be do-able in roughly two hours. The final exam will be released on Monday, March 15 at 2:30 pm (the same time as the final exam would normally be scheduled for this course) and must be submitted by a hard deadline of Wednesday, March 17 at 6:00 pm. Like the midterm exam, your solutions must be handwritten and submitted through Gradescope. (Some submitted midterms had very low contrast which made them hard to read. It is your job to ensure that your submission is sufficiently high contrast!)

    Absolutely no collaboration is allowed for the final exam and no access is allowed to any resources other than the following: this quarter's 421 course slides and videos, the Kleinberg-Tardos textbook, the notes from Manber's text, and homework solutions (posted under Pages on the 421 Canvas website).

    If you have any questions during the final exam, you should send them to the
    cse421-staff@cs.uw.edu mailing list.
    (Access to the Ed discussion board is forbidden during this time.)

    The final exam will be comprehensive. 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, March 14, beginning at 3:00 pm at the following Zoom link.

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