This course studies the major algorithmic design paradigms and mathematical tools for analyzing the running times of algorithms and detecting computational problems for which no efficient deterministic algorithm exists. Topics include: basics of analysis of algorithms; general algorithmic paradigms: (i) divide and conquer; (ii) greedy algorithms; (iii) dynamic programming; and (iv) graph algorithms; NP-completeness and its implications; and undecidability.
This course is an in-person course. Although some material (such as slides used in lectures or notes) maybe provided on the webpage, students are expected to attend lectures. The midterm and final exam are also in-person.
In the event that the university suspends in person activity:Lecture materials (slides) will be posted here. If you are happy to learn from the slides, that's fine. When you need more details/examples, or if you like a text book format, here are the corresponding sections of the text, CLRS, together with our recommendations for alternative sources available online. For descriptions of the books, see Resources.
| Date | Topics | Slides | CLRS | Other readings (* = highly recommended) |
||
|---|---|---|---|---|---|---|
| Week 1 | L1 | Jan 7 | Course Introduction, Review of Asymptotics |
Armin/Collin: Lecture 01
Mark: Lecture 01 |
4.1, 4.3, 4.4, 4.5; Optionally CLRS 2.3 | |
| L2 | Jan 9 | Solving Recurrences |
Armin/Collin: Lecture 02
Mark: Lecture 02 Lec02notes |
4.2 | [DPV] 2 | |
| Week 2 | L3 | Jan 14 | Divide-and-conquer I |
Armin/Collin: Lecture 03
Mark: Divide and Conquer DCnotes |
4.1, 4.3, 4.4, 4.5; Optionally CLRS 2.3 | |
| L4 | Jan 16 | Divide-and-conquer II |
Armin/Collin: Lecture 04
Mark: See L3 for slides and notes |
4.2 | [DPV] 2 | |
| Week 3 | L5 | Jan 21 | Divide-and-conquer III |
Armin/Collin: Lecture 05 (Collin)
Mark: See L3 for slides and notes |
9.3 | |
| L6 | Jan 23 | Graph Algorithms I (intro and BFS) |
Armin/Collin: Lecture 05
Mark: Graphs Graphs Notes 1 Graphs Notes 2 |
22.1, 22.2 | * [Erickson] 5.1 - 5.4 | |
| Week 4 | L7 | Jan 28 | Graph Algorithms II (DFS) |
Armin/Collin: Lecture 06
Mark: |
22.3 | * [Erickson] 5.5, 6.1 |
| L8 | Jan 30 | Graph Algorithms III (directed graphs) |
Armin/Collin: Lecture 07
Mark: |
22.4, 22.5 |
[DPV] 3.2
[Erickson] 6 |
|
| Week 5 | L9 | Feb 4 | Graph Algorithms IV (Dijkstra's algorithm) |
Armin/Collin: Lecture 08
Mark: |
24.1, 24.3 | [Erickson] 8.6 |
| L10 | Feb 6 | Graph Algorithms V (minimum spanning trees) |
Armin/Collin: Lecture 09
Mark: |
23 |
[DPV] 5.1
[Erickson] 7.1, 7.2, 7.5 |
|
| Week 6 | L11 | Feb 11 | Greedy Algorithms I |
Armin/Collin: Lecture 10
Mark: Greedy Algs Greedy Notes |
16.1 | [Erickson] 4 |
| L12 | Feb 13 | Snow Day |
Armin/Collin:
Mark: |
16.2 | ||
| Reading week | ||||||
| Week 7 | Midterm Exam: Monday, Feb 24, 7:00pm to 8:50pm | |||||
| L13 | Feb 25 | Greedy Algorithms II |
Armin/Collin: F24 Lecture 06
Mark: |
intro of 15, 15.3; CLRS 15.1 | Optional [Erickson] 3.1, 3.4 | |
| L14 | Feb 27 | Dynamic Programming I |
Armin/Collin: Lecture 11
Armin's annotated slide Mark: Dynamic Programming Dynamic Programming Notes |
[DPV] 6.4 | ||
| Week 8 | L15 | Mar 4 | Dynamic Programming II |
Armin/Collin: Lecture 12
Armin's annotated slide Mark: |
15.4 | |
| L16 | Mar 6 | Dynamic Programming III |
Armin/Collin: Lecture 13
Armin's annotated slide Mark: |
23 |
[DPV] 5.1
[Erickson] 7.1, 7.2, 7.5 |
|
| Week 9 | L17 | Mar 11 | Dynamic Programming IV |
Armin/Collin: Lecture 14
Armin's annotated slides Mark: |
Lap Chi's notes, 15 | |
| L18 | Mar 13 | NP-completeness I: Reductions |
Armin/Collin: Lecture 15
Armin's annotated slide Mark: Hard Problems Hard Problems Notes |
34.1 |
[DPV] 8
[Erickson] 12 * for reductions: [Erickson] 1.1 |
|
| Week 10 | L19 | Mar 18 | NP-completeness II |
Armin/Collin: Lecture 16
Armin's annotated slide Mark: | ||
| L20 | Mar 20 | NP-completeness III |
Armin/Collin:
Mark: |
34.1 |
[DPV] 8
[Erickson] 12 * for reductions: [Erickson] 1.1 |
|
| Week 11 | L21 | Mar 25 | NP-completeness IV |
Armin/Collin: Lecture 17
Mark: |
34.2 | |
| L22 | Mar 27 | NP-completeness V |
Armin/Collin: Lecture 18
Mark: |
34.3 | ||
| Week 12 | L23 | Apr 1 | NP-completeness VI |
Armin/Collin: Lecture 23
Mark: |
34.4 | |
| L24 | Apr 3 | Misc |
Armin/Collin: Lecture 24
Mark: |
34.5 | ||
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 legible. We have the right to take marks off for illegible answers.
When the CrowdMark instance is ready, all students enrolled in the class will receive an email with a link to their individual submission site. In order to submit, upload a separate PDF file (multiple pages are allowed) to each question. You may resubmit as often as necessary until the due date. (More detailed CrowdMark information is available at https://crowdmark.com/help/completing-and-submitting-an-assignment/.)
Marmoset will be used for the programming questions, and is available at https://marmoset.student.cs.uwaterloo.ca.
Assignments will appear in the following table, and will be due on the dates specified:
| Assignment Number | Date Posted | Due (11:59pm EDT/EST) | Hand In Via | Markers | Solutions |
|---|---|---|---|---|---|
| Assignment 1 PDF LateX | Mon Jan 13 | Fri Jan 24 | CrowdMark | Login required | |
| Assignment 2 PDF | Mon Jan 27 | Fri Feb 7 | CrowdMark | Login required | |
| Programming 1 PDF Public tests | Fri Jan 31 | Fri Feb 14 | Marmoset | ||
| Assignment 3 PDF LaTeX | Fri Feb 21 | Fri March 7 | CrowdMark | Login required | |
| Assignment 4 PDF LaTeX | Fri March 7 | Fri March 21 | CrowdMark | Login required | |
| Programming 2 PDF Public tests | Fri March 14 | Fri March 28 | Marmoset | ||
| Assignment 5 PDF LaTeX | Fri March 21 | Fri April 4 | CrowdMark | Login required |
Instructions for Assignments: Your written solutions will be judged not only for correctness but also for the quality of your presentation and explanations. In questions that involve designing an algorithm, unless specified otherwise, include the following and clearly identify each part (do not mix all of it together, keep each part separate):
In all assignments, unless otherwise directed, you are expected to justify any claims that you make. The level of explanation we generally expect is "enough to convince a skeptical TA". Usually this means that a complete formal proof from first principles is not needed (unless we say so). Furthermore, since this course is essentially all about efficient use of time and space, strive to make your solutions as efficient as possible. Solutions that are technically correct, but extremely wasteful in terms of time and space, will not receive full credit.
Collaboration Policy: The work you hand in must be your own. Unless specified otherwise, you can always use any result from the textbook, notes, or previous assignment just by citing it. You may discuss the assignment questions verbally with others, but you should come away from these discussions with no written or electronic records and you must acknowledge the discussion. Acknowledge any sources you have used. Any assistance received (from human or nonhuman sources) that is not given proper citation may be considered a violation of the university policies.
Programming Questions: Some assignments may have programming questions, where we ask you to code an algorithm. This is not a software engineering course; we will not test your code against inputs that do not match our specifications. However, your program should take care of the edge cases that are crucial to the algorithm's correctness or analysis. For example, unless the problem states so, you should not usually assume that the input size is a power of 2. We will post instructions about how to submit programming questions on Piazza.
Late Policy: Assignments (including programming assignments) can be handed in up to 2 days late, but with a penalty of 25% per day.
Short Term Absences and Other Extenuating Circumstances: If you use a 2-day short term absence that overlaps an assignment deadline, rather than granting an extension, we will waive the late penalties for the assignment. This gives you two extra days to submit without penalty. However, if you submit more than 2 days late, you will get zero.
In general, we cannot grant more than 2 extra days on assignments, as we might post solutions shortly after the late deadline. For longer absences, illnesses with a supporting Verification of Illness Form (VIF), or other extenuating circumstances, we may be able to offer another accommodation, like dropping the assignment and shifting the weight. Contact the Instructional Support Coordinator to discuss your options (see the table of course personnel below).
Note: You must pass the weighted examination portion, in order to pass the course.
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.
Similarly, do not solicit hints or provide hints about how to solve the homework problems on other bulletin boards, such as Facebook. Violations can result in academic sanctions.
Piazza is not the place to dispute how assignments are marked. If you have a complaint, please follow the remark request process.
| Instructor | Email (at school name dot ca) | Office Hours |
|---|---|---|
| Armin Jamshidpey | a5jamshi | Mondays 9:30-11:30 am on MS Teams |
| Mark Petrick | mdtpetri | Tues and Thurs from 10am-11am in MC 6467 ** No Office hours on Tues Feb 4, Mar 4, Apr 1 Often available at 1pm on Tues and Thurs (after lecture in MC 2035) but let me know ahead of time if you want to meet. |
| Collin Roberts | cd2rober | in MC 6459: 2025-04-16, 11:00-12:00, 2025-04-17, 14:00-16:00, or by appointment |
| Instructional apprentice | Email (at school name dot ca) |
|---|---|
| Amirmohammad Ghasemi | a4ghasem |
| Prashant Gokhale | p2gokhal |
| Teaching assistant | Email (at school name dot ca) |
| Omkar Bhalchandra Baraskar | obaraska |
| Jingbang Chen | j293chen |
| Brian Do | bdo |
| Mohammad Hossein Ebtehaj | mhebteha |
| Remy El Sabeh | relsabeh |
| Alireza Fathollah Pour | a2fathol |
| Abhibhav Garg | a65garg |
| Anas Ibrahim | a23ibrah |
| Tiasa Mondol | tmondol |
| Zhiang Wu | z46wu |
IA and TA office hours will be announced on Piazza.
| Instructional support coordinator | Email (at school name dot ca) |
|---|---|
| Sylvie Davies | sldavies |
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 (submit early and
often, even if not finished). 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 marks on CrowdMark/Marmoset. question by email. Details of how to make a request will be posted on Piazza. |
| Assignment Recording Error: | Grades will be made available either through Learn or the course website. Details will be announced on Piazza. If you notice an error in the recorded value, 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: | IA/TA office hours or instructor office hours or Piazza. |
| Lecture Questions: | IA/TA office hours or instructor office hours or Piazza. |
| Missed Work Due To Illness/Valid, Verifiable Reason (Assignments, Exams): | Assignments, midterms, final exam: Validation required (see Verification of Illness Services at https://uwaterloo.ca/campus-wellness/health-services/student-medical-clinic but substitute Sylvie Davies (CS 341 ISC) for references to instructor). Make sure you also read the Math Faculty document on the consequences of submitting a VIF. |
| AccessAbility Services (AAS) exam accommodation forms (request to write at AAS): | Submit to AAS at least 3 weeks before exam. |
If you are person who likes a more detailed text book format, here are our recommendations for sources available online.
Textbook: [CLRS] Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (3rd ed.), MIT Press, 2009 (QA76.6 .C662 2009).
This book is available electronically through the UW library catalog.
Additional reference: [DPV], Dasgupta, Papadimitriou, Vazirani, Algorithms, available here.
Additional books:
The following resource is also useful for the course but more importantly for technical interviews you may have:
Mental Health: If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support.
On-campus Resources
Off-campus Resources
Diversity: It is our intent that students from all diverse backgrounds and perspectives be well served by this course, and that students' learning needs be addressed both in and out of class. We recognize the immense value of the diversity in identities, perspectives, and contributions that students bring, and the benefit it has on our educational environment. Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally or for other students or student groups. In particular:
Academic integrity: In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. [Check the Office of Academic Integrity for more information.]
Grievance: A student who believes that a decision affecting some aspect of their university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70, Student Petitions and Grievances, Section 4. When in doubt, please be certain to contact the department’s administrative assistant who will provide further assistance.
Discipline: A student is expected to know what constitutes academic integrity to avoid committing an academic offence, and to take responsibility for their actions. [Check the Office of Academic Integrity for more information.] A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (e.g., plagiarism, cheating) or about “rules” for group work/collaboration should seek guidance from the course instructor, academic advisor, or the undergraduate associate dean. For information on categories of offences and types of penalties, students should refer to Policy 71, Student Discipline. For typical penalties, check Guidelines for the Assessment of Penalties.
Avoiding Academic Offenses: Most students are unaware of the line between acceptable and unacceptable academic behaviour, especially when discussing assignments with classmates and using the work of other students. For information on commonly misunderstood academic offenses and how to avoid them, students should refer to the Faculty of Mathematics Cheating and Student Academic Discipline Policy, https://uwaterloo.ca/math/current-undergraduates/regulations-and-procedures/cheating-and-student-academic-discipline-guidelines.
MOSS (Measure of Software Similarities) is used in this course as a means of comparing students' assignments to ensure academic integrity. We will report suspicious activity, and penalties for plagiarism/cheating are severe. Please read the available information about academic integrity very carefully.
Discipline cases involving any automated marking system such as Marmoset include, but are not limited to, printing or returning values in order to match expected test results rather than making an actual reasonable attempt to solve the problem as required in the assignment question specification.
Appeals: A decision made or penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes they have a ground for an appeal should refer to Policy 72, Student Appeals.
Note for students with disabilities: AccessAbility Services, located in Needles Hall, Room 1401, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with AccessAbility Services at the beginning of each academic term.
