## CSE 421: Introduction to Algorithms

#### Paul Beame

Lectures
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

 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]

##### 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.

##### Lecture Slides
• 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

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.

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.