CS 341: Algorithms, Fall 2018
David R. Cheriton School of Computer Science
Contents:
General Info,
Organization,
Announcements,
Resources,
Assignments,
Lectures,
University Policies
General Information
You should attend the section in which you are registered. Do not inconvenience other
students by attending other sections. In Sections 1 and 2 cards which give you the right
to a seat will be distributed. If you do not have a card, do not take a seat.
Instructors:
Bin Ma,
DC 3345, x32747, binma@uwaterloo.ca .
Office hours: Monday 35pm (Except for Sept. 17).
Jeffrey Shallit,
DC3134, x34804, shallit@uwaterloo.ca .
Office hours: Mondays and Fridays from 1 PM to 2 PM, or
by appointment, or just stop by DC 3134 whenever my office door is open.
No office hours on Friday September 21, sorry.
Walk with Professor Shallit! Every Monday and Wednesday at noon I'll
go for a 30minute walk, either around the Ring Road, or inside through
the campus bridges and tunnels (depending on the weather). You are invited
to come along, to ask questions about the course material, to ask
questions about anything at all, or just have a chat.
I'll leave exactly at noon (12:00 PM) on those days,
and the route (inside or outside) will be
listed on the bulletin board outside DC 3134.
TAs:

Stavros Birmpilis, sbirmpil@uwaterloo.ca
Office hours: 9 AM  10 AM Mondays, DC 2136B.

Venkata Abhinav Bommireddi, vabommir@uwaterloo.ca
Office hours: 3 PM  4 PM Fridays, DC 2102.
(On September 28 office hours will be in DC 2306C instead.)

Jian Li, j493li@uwaterloo.ca
Head TA
Office hours: 2 PM  3 PM Fridays, DC 2102.

Tiasa Mondol, tmondol@uwaterloo.ca
Office hours: 10 AM  11 AM Fridays, DC 2136B

Azin Nazari, a5nazari@uwaterloo.ca
Office hours: 1 PM  2 PM Tuesdays, DC 3323.

Bryce Christian Sandlund, bcsandlu@uwaterloo.ca
Office hours: 2 PM  3 PM Mondays, DC 2102.

Nolan Shaw, n5shaw@uwaterloo.ca
Office hours: 9 AM  10 AM Tuesdays, DC 2136B

Jia Rong Wu, jr2wu@uwaterloo.ca
Office hours: 4 PM  5 PM Fridays, DC 2102.
(On September 28 office hours will be in DC 2306C instead.)
Time and Place:
First class is THURSDAY, SEPTEMBER 6!
 Section 1: Tuesdays & Thursdays, 2:30 PM  3:50 PM, MC 2038 (Shallit)
 Section 2: Tuesdays & Thursdays, 4:00 PM  5:20 PM, MC 2038 (Shallit)
 Section 3: Tuesdays & Thursdays, 2:30 PM  3:50 PM, MC 2034 (Ma)
 Section 4: Tuesdays & Thursdays, 4:00 PM  5:20 PM, MC 2034 (Ma)
Advice:
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 assignments. Doing
the assignments exercises your neurons so that you are always
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 don't understand how an algorithm works, it is often very helpful
to execute it carefully by hand, on a piece of paper, on a variety of
different inputs.
If you do all these, we guarantee you will pass the course.
Credit:
There will be ten assignments, worth 30% of the course mark. The lowest
mark of the ten assignments will be discarded.
Midterm is Tuesday, October 23 from 7 PM to 9 PM in
AHS 1689 and M3 1006. It is worth 25% of the
course mark. Students should now be able to see their own personal examination schedule, at
https://odyssey.uwaterloo.ca/teaching/schedule.
What to Know for the Midterm
For remarking:
Problem 1 was marked by Prof. Jeffrey Shallit and Abhinav Bommireddi
Problem 2 was marked by Nolan Shaw
Problem 3 was marked by Jia Rong Wu
Problem 4 was marked by Abhinav Bommireddi
Problem 5 was marked by Prof. Jeffrey Shallit, Azin Nazari, and Stavros Birmpilis
Problem 6 was marked by Prof. Bin Ma, Bryce Sandlund, and Tiasa Mondol.
For questions 1, 5, and 6 you can address your questions to the respective instructors who marked them.
Final exam is scheduled to be on Saturday, December 8 2018,
at 12:30 PM  3 PM in STC 0050,0060,1012.
It will be worth 45% of the course mark,
and will focus somewhat more on the 2nd half of the course.
What to Know for the Final
Your final course mark will be determined
from your marks on these three components and nothing else.
In particular, there is no
requirement to pass the final, or midterm,
or average of midterm and final,
in order to pass the course.
 Homework Assignment 1  due Tuesday September 18 at 6 PM. Hand in via
Crowdmark .
Solutions are now available on LEARN, in the Assignments tab, under the
name sol1.pdf .
 Homework Assignment 2  due Tuesday September 25 at 6 PM. Hand in via
Crowdmark .
Solutions are now available on LEARN, in the Assignments tab, under the name sol2.pdf .
 Homework Assignment 3  due Tuesday October 2 at 6 PM. Hand in via
Crowdmark .
Solutions are now available on LEARN, in the Assignments tab, under the name sol3.pdf .
 Homework Assignment 4  due Tuesday October 16 at 6 PM. Hand in via
Crowdmark .
Solutions are now available on LEARN, in the Assignments tab, under the name sol3.pdf .
 Homework Assignment 5  due Tuesday October 23 at 6 PM. Hand in via
Marmoset .
Assignment specs were updated at 6AM on Wed Oct 24 to reflect the fact that
your output should end in \n.
Assignment specs updated again at 10:15 AM on Wed Oct 24 to allow python.
 Homework Assignment 6  due Tuesday October 30 at 6 PM. Hand in via
Crowdmark.
Fixed an error in Q2: L_{i} was changed to L. (Oct. 24, 2pm)
Fixed an error in Q1: "greedy" was changed to "gex". (October 25)
Added clarification that all numbers are positive integers in Q2,Q3,Q4. (Oct. 28)
 Homework Assignment 7  due Tuesday November 6 at 6 PM. Hand in via
Crowdmark.
 Homework Assignment 8  due Tuesday November 13 at 6 PM. Hand in via
Crowdmark.
 Homework Assignment 9  due Tuesday November 20 at 6 PM. Hand in via
Crowdmark and Marmoset (two different parts).
 Homework Assignment 10  due Friday November 30 at 6 PM. Hand in via
Crowdmark.
Q1b was updated at 10:20pm on Mon Nov 26 to
allow running time to be T(2m, 2n)*(mn)^c. Formerly
it was T(m,n)*(mn)^c. This change
should have no impact for students who already have
completed the question. But it makes alternative
solutions possible.
For Assignments 14, and Assignments 68,
hand in a PDF file with your solutions via Crowdmark.
You should prepare your
solutions using a document preparation system such as LaTeX or
(urk!) Microsoft Word. Please do not write solutions by hand and scan them
in.
For figures, on the other hand,
feel free to sketch by hand and scan in the results.
Assignments will be handed out and due as follows:
Assignment
Number Handed out Due Marker
1 Tue Sep 11 Tue Sep 18 Jian (Q1), Abhinav (Q2), Stavros (Q3)
2 Tue Sep 18 Tue Sep 25 Nolan (Q1), Azin (Q2), Tiasa (Q3)
3 Tue Sep 25 Tue Oct 2 Abhinav (Q1), Bryce (Q2), Jia Rong (Q3)
4 Tue Oct 2 Tue Oct 16 Azin (Q1), Jian (Q2), Stavros (Q3, Q4)
5 Tue Oct 16 Tue Oct 23 Jian
6 Tue Oct 23 Tue Oct 30 Tiasa (Q1), Nolan (Q2), Jia Rong (Q3, Q4)
7 Tue Oct 30 Tue Nov 6 Azin (Q1), Bryce (Q2), Abhinav (Q3, Q4)
8 Tue Nov 6 Tue Nov 13 Stavros (Q1), Tiasa (Q2), Nolan (Q3)
9 Tue Nov 13 Tue Nov 20 Jia Rong (Q1, Q3); Jian (Q2)
10 Tue Nov 20 Tue Nov 30 Stavros (Q1), Azin (Q2), Bryce (Q3), Nolan (Q4)
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.
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, Jian Li.
Finally, if you do not get satisfaction from either of those two people, contact the professor of your section.
Algorithmic Challenges
Compiled from the lecture notes, solve any of these
challenges and get an automatic 100 in
the course!
Enrichment
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 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 LEARN.
Textbook:
[CLRS] Cormen, Leiserson, Rivest, and Stein,
Introduction to Algorithms (3rd ed.), MIT Press,
2009 (QA76.6 .C662 2009).
Additional reference:
[DPV], Dasgupta, Papadimitriou, Vazirani, Algorithms, available
here.
Additional books on DC library reserve for 3hour loan:
 [KT] Kleinberg and Tardos, Algorithm Design
(QA76.9.A43K54 2006)
 [BB] Brassard and Bratley, Fundamentals of Algorithmics
(QA9.58.B73 1996)
 [GJ] Garey and Johnson, Computers and Intractability: A Guide to the
Theory of NPCompleteness (QA76.6.G35 1979)
There are three other resources that you might find useful:
 Jeff Erickson's
notes on algorithms at the University of Illinois. Huge collection (don't print it!)
 Adnan Aziz and Amit Prakash, Algorithms for Interviews, 2010.
Available here. Nice small
collection of problems and solutions
 Steven S. Skiena, The Algorithm Design Manual, Springer, 2nd edition, 2010.
Discussion of applying course material to realworld problems.
Finally, you may also enjoy Brian Christian and Tom Griffiths,
Algorithms to Live By: The Computer Science of Human Decisions.
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 Notes for Sections 3 and 4 (Bin Ma) are to be found
here.
Lecture Notes for Sections 1 and 2 (Shallit)
 Lecture 1, Thursday, September 6 2018: Course intro and rules; examples of algorithms; notion of "step"; input size; INSERTIONSORT
 Lecture 2, Tuesday, September 11 2018: BigO, BigTheta, littleo; polynomial time; maximum subrange sum problem
 Lecture 3, Thursday, September 13 2018: Maximum subrange sum; worstcase complexity; paradigms of algorithm design; reduce to known problem
 Lecture 4, Tuesday, September 18 2018: discrete logarithm example; convex hull
 Lecture 5, Thursday, September 20 2018 (guest lecture by Eugene Zima): preprocessing; recursion; computing all permutations
 Lecture 6, Tuesday, September 25 2018: divideandconquer; mergesort; solving recurrences; Karatsuba's algorithm for multiplying large numbers
 Lecture 7, Thursday, September 27 2018: Strassen's algorithm for matrix multiplication; closest pair of points
 Lecture 8, Tuesday, October 2 2018: closest pair of points; dynamic programming; optimal order to multiply matrices; memoization
 Lecture 9, Thursday, October 4 2018: longest common subsequence; subset sum problem
 Tuesday, October 9 2018  no class  study break
 Lecture 10, Thursday, October 11 2018: optimal coinchanging; traveling salesperson; invent/augment data structure
 Lecture 11, Tuesday, October 16 2018: greedy algorithm; making change; scheduling activities; Egyptian fractions; knapsack
 Lecture 12, Thursday, October 18 2018: fractional knapsack; exploit problem's structure; computing the gcd; probabilistic and randomized algorithms
 Lecture 13, Tuesday, October 23 2018: majority element problem; pseudorandom numbers; intro to graphs and graph algorithms
 Lecture 14, Thursday, October 25 2018: how to store graphs; breadthfirst search (BFS)
 Lecture 15, Tuesday, October 30 2018: applications of BFS; depthfirst search (DFS)
 Lecture 16, Thursday, November 1 2018: applications of DFS; topological sort; stronglyconnected components
 Lecture 17, Tuesday, November 6 2018: minimum spanning trees; Kruskal's algorithm; Prim's algorithm
 Lecture 18, Thursday, November 8 2018: shortest paths; BellmanFord algorithm; detecting negative cycles; Dijkstra's algorithm
 Lecture 19, Tuesday, November 13 2018: FloydWarshall algorithm for allpairs shortest paths; P (polynomial time)
 Lecture 20, Thursday, November 15 2018: NP, decision problems, reductions
 Lecture 21, Tuesday, November 20 2018: reductions, polynomialtime reductions, NPcompleteness
 Lecture 22, Thursday, November 22 2018: NPcompleteness of SAT, 3CNFSAT, intro to CLIQUE
 Lecture 23, Tuesday, November 27 2018:
NPcompleteness of CLIQUE, VERTEX COVER, and
and SUBSET SUM. Solvable and unsolvable problems.
 Lecture 24, Thursday, November 29 2018:
More on solvable and unsolvable problems. Awards for the highest
average in each class.
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.
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.
Grievance:
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 .
Discipline:
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/currentundergraduates/regulationsandprocedures/cheatingandstudentacademicdisciplineguidelines.
Appeals:
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.