CS 341: Algorithms

Welcome to the Spring 2024 offering of CS 341. In this course, we will study the design and analysis of algorithms. Topics include:

• Divide and conquer
• Greedy algorithms
• Dynamic programming
• Graph algorithms
• Maximum flow
• NP-completeness

Format

This will be an in-person course, with lectures twice a week in each of two sections:

• Section 001: Tuesdays and Thursdays 2:30pm-3:50pm in MC 2035
• Section 002: Tuesdays and Thursdays 11:30am-12:50pm in MC 2038

The lectures will not be recorded.

All students are also required to join Piazza, where we can all participate in discussions. Important announcements may be made through Piazza.

Office hour information will be posted on Piazza. There will not be office hours the first week of class.

Assessments

The tentative grade breakdown is as follows:

• 5 assignments worth a total of 25%
• A midterm worth 25%
• A final exam worth 50%.

The assignments will be written assignments to be submitted on Crowdmark. There will not be programming assignments in this offering.

Resources

The course outline is here.

The following websites will be associated with the course:

• The course webpage you are currently looking at.
• The Piazza page, found here.
  • All students need to join Piazza, as some announcements may be made exclusively on Piazza.
• The UW Learn page, found here.
• The Crowdmark site. (Registered students will receive an invitation.)
  • The assignments will be submitted and graded through Crowdmark.

Readings that correspond to each lecture will be posted on Piazza. They will usually refer to the online textbook Algorithms by Jeff Erickson, available here. Additional optional resources that may be of interest include:

• Lap Chi Lao’s CS 341 lecture notes, found here.
• Slides for CS 341 by Trevor Brown and separate slides by Rafael Oliveira, found here.
• Introduction to Algorithms, a textbook by Cormen, Leiserson, Rivest, and Stein. A PDF appears to be available here.
• Algorithm Design, a textbook by Kleinberg and Tardos. A PDF appears to be available here.
• Algorithms, a textbook by Dasgupta, Papadimitriou, and Vazirani. A PDF appears to be available here.

Please note that while the last 3 links appear to be hosted at educational institutions, I could not get confirmation regarding the copyright status of the linked PDFs; I will remove the links if I get notice that they infringe copyright. The only book which is confirmed free to use is Jeff Erickson’s, so we will use that one for this course.

Schedule

The following is tentative and subject to change. Assignments are currently planned to be due approximately every other week on Fridays.

• Week of May 6: Lecture 1 on Tue. May 7, Lecture 2 on Thu. May 9
  • Tuesday May 7 is the first day of class for this course.
• Week of May 13: Lecture 3 on Tue. May 14, Lecture 4 on Thu. May 16
  • Friday May 17 is the last day to officially enroll in the class.
• Week of May 20: No class Tuesday. Lecture 5 on Thu. May 23
  • Monday May 20 is Victoria Day (no classes).
  • Tuesday May 21 is Monday schedule (no class for CS 341).
  • Assignment 1 due Friday May 24.
• Week of May 27: Lecture 6 on Tue. May 28, Lecture 7 on Thu. May 30
  • Monday May 27 is the last day to drop the class without a mark on the transcript.
• Week of June 3: Lecture 8 on Tue. June 4, Lecture 9 on Thu. June 5
  • Assignment 2 due Friday June 7.
• Week of June 10: Lecture 10 on Tue. June 11, Lecture 11 on Thu. June 13
• Week of June 17: Lecture 12 on Tue. June 18, Lecture 13 on Thu. June 20
  • Midterm is Monday June 17, 4:30pm-6:20pm.
• Week of June 24: Lecture 14 on Tue. June 25, Lecture 15 on Thu. June 27
  • Assignment 3 due Friday June 28.
• Week of July 1: Lecture 16 on Tue. July 2, Lecture 17 on Thu. July 3
  • Monday July 1 is Canada Day (no classes); we still have a class on Tuesday as normal.
• Week of July 8: Lecture 18 on Tue. July 9, Lecture 19 on Thu. July 11
  • Assignment 4 due Friday July 12.
• Week of July 15: Lecture 20 on Tue. July 16, Lecture 21 on Thu. July 18
  • Tuesday July 16 is the last day to drop with a WD.
• Week of July 22: Lecture 22 on Tue. July 23, Lecture 23 on Thu. July 25
  • Assignment 5 due Friday July 26.
• Week of July 29: Lecture 24 on Tue. July 30
  • Classes end Tuesday July 30 (no class Thursday August 1).
• Final Exam to be scheduled between August 2 and August 16.