CS 341: Algorithms, Fall 2016
Crosslisted as CM 339.
David R. Cheriton School of Computer Science
DC3134, x34804, (sorry, but to foil spammers, that's not a cut-and-pastable link)
Office hours: Mondays, 11 AM - Noon; Wednesdays, Noon - 1 PM, or
by appointment, or just stop by when my office door is open.
Scheduled office hours begin Monday, September 12.
In addition I will hold "virtual office hours" every Wednesday night
from 9 PM to 10 PM via AOL Instant Messenger. I use the id "CS462Prof".
This is a good way to get last-minute help (and even anonymously, if you
Tim Smith, DC 3124, x33319, email@example.com
Office hours: 4:30-6:30 PM Tuesdays
Time and Place:
- Hong Zhou (Head TA), firstname.lastname@example.org, DC 3115. Office hours: Tuesdays, 3:30 - 4:30 PM.
- Vedat Levi Alev, email@example.com, DC 3115. Office hours: Mondays,
3:30 - 4:30 PM.
- Kirsten Bradley, firstname.lastname@example.org . Kirsten is helping us mark
- Hassan Ashtiani, email@example.com , x33602, DC 3519.
Office hours: Wednesdays, 3-4 PM
- Shayan Hassantabar, firstname.lastname@example.org, DC 3549. (You may need
to ring the bell outside the office.) Office hours: Wednesdays, 1 - 2 PM.
First class is THURSDAY, SEPTEMBER 8!
- Section 1: Tuesdays & Thursdays, 11:30 AM - 12:50 PM, PAS 1229 (Shallit)
- Section 2: Tuesdays & Thursdays, 8:30 AM - 9:50 AM, MC 2034 (Shallit)
- Section 3: Tuesdays & Thursdays, 1:00 PM - 2:20 PM, PAS 1229 (Smith)
- Section 4: Tuesdays & Thursdays, 8:30 AM - 9:50 AM, PHYS 313 (Smith)
Many students find CS 341 a challenging course. But there is a relatively
simple path to success. Here's how to do well in the course:
First, come to all the classes. Students who fail the course almost always
have poor attendance.
Next, do all the assignments. Students who fail the course almost always
do so because they hand in only a few of the 12 homework assignments. Doing
the assignments exercises your neurons so that you are in the mode of thinking
about the course material -- this will also help you understand better in class,
and do well in the midterm and final.
Finally, allocate 3 hours per week to go over the course notes, try the
suggested exercises, and read the assigned sections of the textbook. Circle
anything you don't understand well and see a TA or instructor to clear
up any difficulties. Do as many supplementary exercises as possible!
If you do all these, we guarantee you will pass the course.
Assignments 36%, Midterm 20%, Final 44%. Your final mark is determined
from your marks on these and nothing else. In particular, there is no
requirement to pass the final in order to pass the course.
Turn in your assignments, in pdf format, via LEARN. You should prepare your
solutions using a document preparation system such as LaTeX or
Microsoft word. Please do not write solutions by hand and scan them
in, unless your handwriting is really superb.
For figures, feel free to sketch by hand and scan in the results.
- Assignments 36% -- see dates below.
- Midterm 20% -- Tuesday, October 25 2016, 7 PM - 9 PM, STC 1012 and 0040.
Pick either room, any seat.
You can bring one sheet of paper to the exam with anything on it. Both
sides may be used. No other aids allowed. In particular, no computers,
calculators, tablets, phones, or electronic devices.
Do not bring phones!
Here is some information about the midterm.
- Midterm solutions (requires same username
and password given in class for the assignment solutions)
If you have a complaint about the midterm marking, follow the same
instructions as for assignments (below). You must request remarking
within two weeks after the midterm is returned.
- Final Exam 44% -- 7:30 PM to 10:00 PM in PAC 1,2,3 on December 12 2016.
Here is some information about the final.
There will be two review sessions for the final. Come to one, both, neither,
as you like:
- Wednesday December 7, 3 PM to 5 PM in AHS 1689 (Shallit)
- Sunday, December 11, from 1 PM to 3 PM in AHS 1689 (Smith)
Assignments will be given out on Thursdays and will be due at 5 PM
on Thursdays, according to the following schedule:
Assignment number Handed out Due Marker
1 September 8 September 15 Shayan and Vedat
2 September 15 September 22 Q1 Vedat; Q2 Shayan; Q3,Q4 Hong
3 September 22 September 29 Q1 Vedat; Q2 Hong; Q3 Shayan
4 September 29 October 6 Q1 Shayan; Q2 Vedat; Q3-Q6 Hong
5 September 29 October 13 Hassan
6 October 13 October 20 Q1 & Q4, Kirsten; Q2 & Q3, Hong
7 October 20 October 27 Q1 & Q2, Vedat; Q3 & Q4, Shayan
8 October 27 November 3 Q1 Hassan, Q2-Q4 Hong
9 November 3 November 10 Q1 Hong; Q2 Kirsten; Q3 Vedat
10 November 10 November 17 Q1 Kirsten; Q2 Hong; Q3 Shayan
11 November 17 November 24 Q1 & Q3, Hassan; Q2 Kirsten
12 November 24 December 1 Q1 Shayan; Q2 Hong; Q3 Vedat
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, or previous
course, just by citing it.
- Problem Set 1, handed out September 8 2016
- Problem Set 2, handed out September 15 2016
- Problem Set 3, handed out September 22 2016
- Problem Set 4, handed out September 29 2016,
due October 6
- Problem Set 5, handed out September 29 2016,
due October 13
Solutions from the class:
- Problem Set 6, handed out October 13 2016,
due October 20
- updated October 14, 9:00 PM (reworded for clarity)
- updated October 16, 1:45 PM (added explanation
of what operations you can use)
- solutions (password protected)
- Problem Set 7, handed out October 13 2016,
due October 27
- Problem Set 8, handed out October 20 2016,
due November 3
- Problem Set 9, handed out November 3 2016
- latex source
(In problem 1 you can assume the array elements are distinct.)
- solutions (password protected)
- Problem Set 10, handed out November 10 2016
- Problem Set 11, handed out November 17 2016
- Problem Set 12, handed out November 24 2016
- latex source
(updated Fri Nov 25 at 10:30 AM to add comment about input size in
(Updated Mon Nov 27 at 5:30 PM to add comment about cycles in problem 1)
- solutions (password protected)
Since solutions are 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
about trivial edge cases (such as the case of empty input), or inputs
that do not match our specifications. We will not take off marks for code
that doesn't handle edge cases correctly (unless they are crucial
to correctness or analysis). In your
solutions, there is no need to spend any time dealing with these (unless
you want to).
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.
If you have a question or complaint about how your assignment or exam was marked,
please start by contacting the TA who marked your assignment or exam. This
can be determined either by consulting the initials written on your assignment, or by looking
on the course home page. Make arrangements to see this TA to discuss your assignment. You must make initial contact with the TA within one week from the day
your assignment is returned.
If you do not get satisfaction from the person who marked your assignment, or if you cannot determine who did, please contact the head TA, Hong Zhou.
Finally, if you do not get satisfaction from either of those two people, contact the professor of your section.
Your single lowest mark out of the 12 assignments will be thrown out*, so
you can (if you choose) not hand in 1 of the 12 assignments.
* This does not apply if you were caught
cheating on an assignment.
On the last day of classes, a prize will be given to the student in
each section with the highest average so far.
Compiled from the lecture notes, solve any of these
challenges and get an automatic 100 in
See this page for additional readings of
interest for each lecture.
We will not use the newsgroup
uw.cs.cs341. Instead 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 extremely detailed advice. We'll delete
comments that reveal too much. Violations can result in
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.
Marks will be available through LEARN.
[CLRS] Cormen, Leiserson, Rivest, and Stein,
Introduction to Algorithms (3rd ed.), MIT Press,
2009 (QA76.6 .C662 2009).
[DPV], Dasgupta, Papadimitriou, Vazirani, Algorithms, available
Additional books on DC library reserve for 3-hour loan:
- [KT] Kleinberg and Tardos, Algorithm Design
- [BB] Brassard and Bratley, Fundamentals of Algorithmics
- [GJ] Garey and Johnson, Computers and Intractability: A Guide to the
Theory of NP-Completeness (QA76.6.G35 1979)
We are not following the text exactly, so the lecture notes
should be your primary source. These are preliminary notes and
might be revised as the term progresses, so check back.
- Lecture 1, Thursday, September 8 2016
- Lecture 2, Tuesday, September 13 2016
- Lecture 3, Thursday, September 15 2016
- Lecture 4, Tuesday, September 20 2016
- Lecture 5, Thursday, September 22 2016
- Lecture 6, Tuesday, September 27 2016
- Lecture 7, Thursday, September 29 2016
- Lecture 8, Tuesday, October 4 2016
- Lecture 9, Thursday, October 6 2016
- Lecture 10, Thursday, October 13 2016
- Lecture 11, Tuesday, October 18 2016
- Lecture 12, Thursday, October 20 2016
- Lecture 13, Tuesday, October 25 2016
- Lecture 14, Thursday, October 27 2016
- Lecture 15, Tuesday, November 1 2016
- Lecture 16, Thursday, November 3 2016
- Lecture 17, Tuesday, November 8 2016
- Lecture 17a: due to lack of time, we weren't able to present this material. You won't be responsible for it, but you might
find it interesting reading.
- Lecture 18, Thursday, November 10 2016
- Lecture 19, Tuesday, November 15 2016
- Lecture 20, Thursday, November 17 2016
- Lecture 21, Tuesday, November 22 2016
- Lecture 22, Thursday, November 24 2016
- Lecture 23, Tuesday, November 29 2016
- Lecture 24, Thursday, December 1 2016
- Lecture 25
Plagiarism is a serious offence. The penalty for the first offence is
0 on the assignment and a further 5 marks off the final course grade.
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.
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 (
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,
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.
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 .
Here is a page we are required to give
you, even though all the same info is above.