[UW Logo]

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.



  Bin Ma, DC 3345, x32747, binma@uwaterloo.ca .
Office hours: Monday 3-5pm (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 30-minute 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.


Time and Place:

First class is THURSDAY, SEPTEMBER 6!


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.


For Assignments 1-4, and Assignments 6-8, 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:

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!


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 3-hour loan:

There are three other resources that you might find useful:

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)


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.

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.


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.