CS 341: Algorithms Winter 2020

We are not following the text exactly. Lecture notes are included below, along with references to the corresponding sections in the course textbook.

Dates Topics & Reading Lecture Brown/Levi Zima
Week 1: Jan 6-10 Overview, Examples of Algorithmic Design Paradigms (CLRS 1,2)
Math Review: Asymptotic Notation, Loop Analysis, Recurrences (CLRS 3)
1 v1: PowerPoint (better), PDF PDF
2 v2: PowerPoint (better), PDF PDF
Week 2: Jan 13-17 Reductions, Recurrences (CLRS 4.3-4.6), Divide & Conquer (CLRS 4.2) 3 v2: PowerPoint (better), PDF PDF
4 v2: PowerPoint (better), PDF PDF
Week 3: Jan 20-24 5 v2: PowerPoint (better), PDF PDF
6 v2: PowerPoint (better), PDF PDF
Week 4: Jan 27-31 Greedy algorithms (CLRS 16.1, 16.2) 7 v2: PowerPoint (better), PDF PDF
8 v2: PowerPoint (better), PDF PDF
Week 5: Feb 3-7 Greedy algorithms 9 v2: PowerPoint (better), PDF PDF
10 v2: PowerPoint (better), PDF PDF
Week 6: Feb 10-14 Dynamic Programming (CLRS 15.1-15.3) 11 v2: PowerPoint (better), PDF
12 v1: PowerPoint (better), PDF
Week 7: Feb 24-28 Dynamic Programming and Graphs (CLRS 22.4-22.5, 23.1-23.2) 13 v1: PowerPoint, PDF PDF
14 v1: PowerPoint, PDF PDF
Week 8: Mar. 2-6 Dynamic Programming and Graphs (CLRS 24.1-24.3, 25.1-25.2) 15 v2: PowerPoint, PDF PDF
16 v1: PowerPoint, PDF PDF
Week 9: Mar. 9-13 Graphs and Intractability 17 v2: PowerPoint, PDF PDF
18 v1: PowerPoint, PDF PDF
Week 10: Mar. 23-27 Graphs and Intractability 19 v3: PowerPoint, PDF, YouTube or MKV
Corrections: YouTube or MKV
20 v2: PowerPoint, PDF, YouTube or MKV
Week 11: Mar. 30 - Apr. 3 Intractability (polynomial transformations) 21-22 (A) v1: PowerPoint, PDF, YouTube or MKV
Intractability (NP completeness, NPC reductions) 21-22 (B) v1: PowerPoint, PDF, YouTube or MKV
Intractability (NPC, NP hardness, undecidability) 21-22 (C) v1: PowerPoint, PDF, YouTube or MKV


Calendar description
Official course description from the course calendar
Handbook description
Longer course description from the Computer Science Undergraduate Handbook


Instructor Email Office Office hours
Trevor Brown trevor.brown@uwaterloo.ca DC 2338 Mondays 5:30-6:30pm
Amit Levi amit.levi@uwaterloo.ca Jan. 15 DC 3102; Jan. 22-Mar. 31 DC 2136A Wednesdays 9-10am
Eugene Zima ezima@uwaterloo.ca DC 2130 Thursdays 4-5pm

Instructional apprentice Email
Vijay Menonv3menon@uwaterloo.ca
Akshay Ramachandrana5ramach@uwaterloo.ca
Hong Zhouh76zhou@uwaterloo.ca

Teaching assistant Email
Aseem Raj Baranwalarbaranw@uwaterloo.ca
Stavros Birmpilissbirmpil@uwaterloo.ca
Pavle Bulatovicpbulatov@uwaterloo.ca
Amelia Holcombaholcomb@uwaterloo.ca
MohammadReza Karegarmkaregar@uwaterloo.ca
Mohammadali Niknamianmniknami@uwaterloo.ca
Karthik Rameshk6ramesh@uwaterloo.ca
Shikhar Sakhujas2sakhuj@uwaterloo.ca
Graeme Robinson Stroudgrstroud@uwaterloo.ca

Instructional support coordinator Email Office
Caroline Kierstead caroline.kierstead@uwaterloo.ca DC 3127 x36226

Lecture schedule

Section Lecture time Room Instructor
LEC 0014:00-5:20 MWMC 2017Trevor Brown
LEC 0022:30-3:50 MWMC 2017Trevor Brown
LEC 00311:30-12:50 TThMC 2034Amit Levi
LEC 0042:30-3:50 TThMC 4021Eugene Zima
LEC 00510:00-11:20 TThMC 2034Amit Levi

Tutorial schedule

Tutorials start the week of January 6.

Section Lecture time Room
10112:30 FMC 2034
10211:30 FMC 2034
1039:30 FMC 2054
1041:30 FMC 2034
1052:30 FMC 2034

Office hours

During the lecture period (lectures end April 3rd):

Mark breakdown

Note that you must pass the weighted exam average in order to pass the course.

Component Weight (%)
Assignments30 (5x6%)
Midterm Exam (Feb. 25, 7-8:50pm, M3 1006, MC 2038, DC 1350)25
Final Exam (scheduled by Registrar's Office)45

Points of contact for common questions

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 late or 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: Re-mark request, due within one week of release of marks on MarkUs/CrowdMark/Marmoset. Contact the TA who marked the specific question and submit a written request. See TAs for contact information.
Course Website Error: Email CS341 course account
Handouts Error: Instructors - email or check consulting hours listed at
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.
Exam Seat (Midterms & Final): Assigned seating. See https://odyssey.uwaterloo.ca/teaching/schedule.
General Course Help: TA office hours or instructor office hours.
Lecture Questions: TA office hours or instructor office hours.
Midterm Remarks: For complaints about exam marking, you need to submit the written request to your section's instructor.
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 Caroline Kierstead (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

Hand in a PDF file with your solutions via the specified website. 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 be handed out and due as follows (dates are tentative and may change):

Assignment Number Due Hand In Via Markers Solutions
PDF, LaTeX template
Jan. 27, 6pm CrowdMark Q1: Mohammadali Niknamian
Q2: MohammadReza Karegar
Q3: Pavle Bulatovic
Q4: Shikhar Sakhuja
Q5: Stavros Birmpilis
See A1 solution sketch under "Assignments" in Learn.
PDF, LaTeX template
Feb. 10, 6pm CrowdMark Q1: Stavros Birmpilis
Q2: Amelia Holcomb
Q3: Mohammadali Niknamian
Q4: Aseem Raj Baranwal
Q5: Graeme Robinson Stroud
Q6: Karthik Ramesh
See A2 solution sketch under "Assignments" in Learn.
PDF, LaTeX template
Mar. 2, 6pm CrowdMark, Marmoset Q1: Karthik Ramesh
Q2: Pavle Bulatov
Q3: MohammadReza Karegar
Q4: Stavros Birmpilis
See A3 solution sketch under "Assignments" in Learn. Note that problem 3 has a linear time solution.
PDF, LaTeX template
Mar. 23, 6pm CrowdMark Q1: Shikhar Sakhuja
Q2: Mohammadali Niknamian
Q3: Amelia Holcomb
Q4: Aseem Raj Baranwal
Q5: Stavros Birmpilis
5 PDF, LaTeX template Apr. 3, 6pm CrowdMark, Marmoset

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, (i) describe the main idea first, (ii) present clearly written pseudocode (e.g., at a level of details mimicking the style of the lectures, the model solutions, or the textbook), (iii) give a correctness proof/argument if it is not immediately obvious, and (iv) include an analysis (usually, of the running time).

The work you hand in must be your own. Acknowledge any sources you have used. Unless specified otherwise, you can always use any result from the textbook, notes, previous assignment, or previous course, just by citing it.

Since solutions will be posted almost immediately online, late assignments will not be accepted under any circumstances. No extensions!

In all assignments and exams, 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.

This is not a software engineering course. We will basically never worry about trivial edge cases (such as the case of empty input), or inputs that do not match our specifications. We will not test such trivial edge cases for the programming assignments, and therefore will not take off marks for code that doesn't handle these trivial edge cases correctly. In your solutions, there is no need to spend any time dealing with these (unless you want to). 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.

The default in this course is that all numbers we deal with are integers. If there are exceptions, we'll let you know.

Some of the algorithms we will discuss in this class have multiple versions and variations. All assignment and exam questions deal with the versions we present. If you choose to learn the material from other sources, such as Wikipedia, rather than from the course notes and textbook, be aware that sometimes these minor differences may affect the answers.

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 on DC library reserve for 3-hour loan:

There are three other resources that you might find useful:

We will use Piazza for all course announcements. 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 process given above.

Marks will be available through https://www.student.cs.uwaterloo.ca/~cs341/cgi-bin/displayMarks.cgi.


Plagiarism is a very serious academic offence and is penalized accordingly. When you plagiarize you damage the learning experience for yourself and others. To avoid plagiarism accusations, do not copy other people's work, and cite all references that you use. If you work with others, only discuss general aspects of the course material, not specific solutions. Write up the solutions yourself, not in groups.

Mental Health Resources

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:

University Policies (University required text)

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. All members of the UW community are expected to hold to the highest standard of academic integrity in their studies, teaching, and research. The Office of Academic Integrity's website ( http://www.uwaterloo.ca/academicintegrity) contains detailed information on UW policy for students and faculty. This site explains why academic integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in - and out - of the classroom.

A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70 - Student Petitions and Grievances, Section 4, http://www.adm.uwaterloo.ca/infosec/Policies/policy70.htm .

A student is expected to know what constitutes academic integrity, to avoid committing academic offenses, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about "rules" for group work/collaboration should seek guidance from the course professor, academic advisor, or the Undergraduate Associate Dean. When misconduct has been found to have occurred, disciplinary penalties will be imposed under Policy 71 - Student Discipline. For information on categories of offenses and types of penalties, students should refer to Policy 71 - Student Discipline, http://www.adm.uwaterloo.ca/infosec/Policies/policy71.htm.

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 or MarkUs 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.

A student may appeal the finding and/or penalty in a decision made under Policy 70 - Student Petitions and Grievances (other than regarding a petition) or Policy 71 - Student Discipline if a ground for an appeal can be established. Read Policy 72 - Student Appeals, http://www.adm.uwaterloo.ca/infosec/Policies/policy72.htm .

Course Outline
According to UW rules, we must also point you to this course outline, although most of the information included in it is already repeated above.