Most information that was historically on the course webpage has now been moved to the Course Outline. The course webpage will still be used for posting lecture notes and assignments.
Below is a schedule of lectures and accompanying notes. Some additional suggested readings are also included for more details and examples. See Resources for more information on the sources for additional readings and further suggestions.
| Date | Topic | Additional Readings | ||
|---|---|---|---|---|
| Week 1 | L1 | Sep 10 | Introduction | [Skiena] 1, 2 |
| Week 2 | L2 | Sep 15 | Solving Recurrences | |
| L3 | Sep 17 | Divide & Conquer | [DPV] 2 | |
| Week 3 | L4 | Sep 22 | More Divide & Conquer | |
| L5 | Sep 24 | Breadth-First Search | ||
| Week 4 | L6 | Sep 29 | Depth-First Search | |
| L7 | Oct 1 | Directed Graphs | ||
| Week 5 | Midterm 1: Monday, Oct 5, 6:00pm to 7:50pm | |||
| L8 | Oct 6 | Directed Graphs (continued) | ||
| L9 | Oct 8 | Greedy Algorithms for Scheduling | ||
| Week 6 | Reading week | |||
| Week 7 | L10 | Oct 20 | Single-Source Shortest Path | |
| L11 | Oct 22 | Minimum Spanning Trees | ||
| Week 8 | L12 | Oct 27 | Dynamic Programming | |
| L13 | Oct 29 | Dynamic Programming (continued) | ||
| Week 9 | L14 | Nov 3 | Dynamic Programming II | |
| L15 | Nov 5 | Dynamic Programming on Trees | ||
| Week 10 | Midterm 2: Monday, Nov 9, 6:00pm to 7:50pm | |||
| L16 | Nov 10 | Dynamic Programming on Graphs | ||
| L17 | Nov 12 | Maximum Flow / Minimum Cut | ||
| Week 11 | L18 | Nov 17 | Maximum Flow / Minimum Cut (continued) | |
| L19 | Nov 19 | Applications of Max Flow/Min Cut | ||
| Week 12 | L20 | Nov 24 | Applications of Max Flow/Min Cut (continued) | |
| L21 | Nov 26 | Polynomial-Time Reductions | ||
| Week 13 | L22 | Dec 1 | NP-Completeness | |
| L23 | Dec 3 | Hard Graph Problems | ||
| Week 14 | L24 | Dec 8 | Hard Partitioning Problems | |
Hand in a PDF file with your solutions via CrowdMark. We encourage you to prepare your solutions using LaTeX but you can use other software or submit handwritten assignments as long as they are clearly legible. We have the right to take marks off for illegible answers.
Assignments will appear in the following table, and will be due on the dates specified:
| Assignment | Date Posted | Due (11:59pm EDT/EST) | Hand In Via | |
|---|---|---|---|---|
| Assignment 1 | Sep 16 | Sep 25 | CrowdMark | |
| 2 | Oct 30 | CrowdMark | ||
| 3 | Nov 20 | CrowdMark | ||
| 4 | Dec 4 | CrowdMark |
See the Course Outline for assignment policies.
We will use Piazza for all course announcements and as a forum for students to ask and answer questions. So you should enroll yourself at your earliest convenience. During Piazza discussions, please do not reveal the solutions to the assignments by requesting or offering detailed advice. We'll delete comments that reveal too much. Violations can result in academic sanctions.
See the Course Outline for information about instructors, TAs/IAs, and other course staff, including contact information.
Note: If you decide to e-mail the course staff, you must use your uwaterloo Quest e-mail account (WatIAM/Quest userID @uwaterloo.ca); otherwise we cannot verify who you are and are limited on what we can accept and respond to.
| Help Topic | Contact |
|---|---|
| Assignment, Missed Deadline: | We do not accept emailed assignments. The last files submitted before the deadline will be marked. If the deadline is missed due to illness or other valid, verifiable reason, see Missed Work Due To Illness below. |
| Assignment Marking Error: | Remark requests are due within one week of release of the remark request form for the assignment, which is typically one or two business days after the release of assignment grades. Details of how to make a request will be posted on Piazza. |
| Assignment Recording Error: | Grades will primarily be made available through CrowdMark. If you notice an error in the recorded grade (e.g., an incorrectly applied late penalty) please contact Sylvie Davies (CS 341 ISC). |
| Course Website Error: | Contact Sylvie Davies (CS 341 ISC). |
| Enrollment: | If Quest won't let you enroll or switch LEC or TUT sections without a permission/override number: Instructors and course staff are unable to help you. You must see a CS academic advisor. |
| General Course Help: | Office hours or Piazza. |
| Lecture Questions: | Office hours or Piazza. |
| Missed Work Due To Illness/Valid, Verifiable Reason (Assignments, Exams): | Assignments, midterms, final exam: Contact Sylvie Davies (CS 341 ISC). |
| AccessAbility Services (AAS) exam accommodation forms (request to write at AAS): | Submit to AAS at least 3 weeks before exam. |
There are many good textbooks and online resources to complement the material that we cover in class. Some recommended resources that cover much of the course syllabus include:
For books that add to the material on NP-completeness and intractability in the last part of the course, see: