[UW Logo]

CS 341: Algorithms, Winter 2019

David R. Cheriton School of Computer Science

Contents: General Info, Organization, Lectures, Assignments, Announcements, Other Information and University Policies

General Information

You should attend the section in which you are registered. Do not inconvenience other students by attending other sections.



Trevor Brown, DC 2338, trevor "dot" brown "at" uwaterloo "dot" ca.
Office hours: Mondays 3-4pm

Semih Salihoglu, DC3351, semih "dot" salihoglu "at" uwaterloo "dot" ca.
Office hours: Thursdays at 4pm.

Doug Stinson, DC 3522, dstinson "at" uwaterloo "dot" ca.
Office hours: Tuesdays 11am-12pm


TA's Name Contact
Vedat Alev vlalev@uwaterloo.ca
Kaleb Alway kpalway@uwaterloo.ca
Aseem Baranwal arbaranw@uwaterloo.ca
Stavros Birmpilis sbirmpil@uwaterloo.ca
Zhengkun Chen z283chen@uwaterloo.ca
Nathaniel Harms nharms@uwaterloo.ca
Tiasa Mondol tmondol@uwaterloo.ca
Azin Nazari a5nazari@uwaterloo.ca
Akshay Ramachandran a5ramach@uwaterloo.ca
Hong Zhou h76zhou@uwaterloo.ca

Time and Place:


Section Lecture Time Room Instructor
LEC 001 11:30-12:50 TTh MC 2054 Semih Salihoglu
LEC 002 02:30-03:50 TTh MC 2038 Semih Salihoglu
LEC 003 04:00-05:20 TTh PHY 235 Douglas R Stinson
LEC 004 01:00-02:20 TTh MC 2035 Douglas R Stinson
LEC 005 04:00-05:20 TTh E2 1736 Trevor Brown


Tutorials start on Friday, January 11.

Section Time Room
TUT 101 03:30-04:20F MC 4060
TUT 102 02:30-03:20F MC 4041
TUT 103 08:30-09:20F MC 1056
TUT 104 01:30-02:20F MC 4063
TUT 105 09:30-10:20F MC 4041
TUT 106 12:30-01:20F MC 4063
TUT 107 11:30-12:20F MC 4042

TA Office Hours:

Wednesday, January 23: 10:30am-11:30am, DC 3102
Friday, January 25: 11:30am-12:30pm, DC 3126

After the first week, all Friday office hours will be in DC 2136A and DC 2136B. We couldn't obtain DC 2136B for all of the Wednesday consulting hours, so the alternate room (in addition to DC2136A) is listed beside each date below.

Mark Breakdown:

Assignments (30%): There will be five assignments.
Midterm (25%): Tuesday, February 26 from 7 PM to 8:50 PM in MC1085, MC4020, MC4021, DC1350, and DC1351. Students are assigned seating, so please check your seat at https://odyssey.uwaterloo.ca/teaching/schedule.
Final (45%): Monday, April 15, 7:30-10pm, PAC 4-8
Students are assigned seating, so please check your seat at https://odyssey.uwaterloo.ca/teaching/schedule.

Your final course mark is a weighted average of the above three components.


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.
Week Topics & Reading Dates Brown Salihoglu Stinson
1 Overview, Examples of Algorithmic Design Paradigms (CLRS 1,2)
Math Review: Asymptotic Notation, Loop Analysis, Recurrences (CLRS 3)
Tuesday, Jan. 8 PDF, PowerPoint PDF, PowerPoint Revised PDF,
supplementary note (PDF)
Thursday, Jan. 10 PDF, PowerPoint, Required background PDF, PowerPoint
2 Asymptotic Notation (CLRS 3), Recurrences (CLRS 4.3-4.6), Reductions
(Some sections may cover example Divide & Conquer algorithms)
Tuesday, Jan. 15 PDF, PowerPoint (Please See Doug & Trevor's Notes on Math Review & Recurrences) Revised PDF
Thursday, Jan. 17 PDF, PowerPoint
3 D & C Example Computational Problems and Algorithms (CLRS 4.2, DPV 2.1) Tuesday, Jan. 22 PDF, PowerPoint PDF, PowerPoint
Thursday, Jan. 24 v2: PDF, PowerPoint
4 D & C Finish (DPV 2.1) & Greedy Algorithms 1 (CLRS 16.1, 16.2) Tuesday, Jan. 29 v1: PDF, PowerPoint PDF, PowerPoint note2.pdf
Revised Greedy Algorithm PDF
Thursday, Jan. 31 v2: PDF, PowerPoint PDF, PowerPoint
5 Greedy Algorithms Finish (CLRS 16.1, 16.2) Tuesday, Feb. 5 v2: PDF, PowerPoint PDF, PowerPoint
Thursday, Feb. 7 v2: PDF, PowerPoint
6 Dynamic Programming (CLRS 15.1-15.3) Tuesday, Feb. 12 Snow day PDF, PowerPoint PDF
Thursday, Feb. 14 v4: PDF, PowerPoint (updated coin changing complexity *again*) PDF, PowerPoint
7 Dynamic Programming and Graphs Tuesday, Feb. 26 v1: PDF, PowerPoint Revised PDF
Thursday, Feb. 28 v1: PDF PDF, PowerPoint
8 Graphs (CLRS 22.4-22.5, 23.1-23.2) Tuesday, Mar. 5 v2: PDF, PowerPoint
v2: PDF, PowerPoint
PDF, PowerPoint
Thursday, Mar. 7 v1: PDF, PowerPoint
v2: PDF, PowerPoint
PDF, PowerPoint
9 Graphs (CLRS 24.1-24.3, 25.1-25.2) Tuesday, Mar. 12 v1: PDF, PowerPoint PDF, PowerPoint
Thursday, Mar. 14 v2: PDF, PowerPoint
10 Graphs (CLRS 24.1-24.3, 25.1-25.2) Tuesday, Mar. 19 v1: PDF, PowerPoint PDF, PowerPoint
Thursday, Mar. 21 v2: PDF, PowerPoint
11 NP Completeness (CLRS ?) Tuesday, Mar. 26 v3: PDF, PowerPoint PDF, PowerPoint Revised: PDF
Thursday, Mar. 28 v2: PDF, PowerPoint PDF, PowerPoint
12 NP Completeness (CLRS ?) Tuesday, Apr. 2 v2: PDF, PowerPoint
Thursday, Apr. 4 v2: PDF, PowerPoint PDF, PowerPoint


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 JPEG or PDF file (multiple pages are allowed) to each question. Please submit a separate file for each question to make the markers' lives easier! You may resubmit as often as necessary until the due date. (More detailed CrowdMark information is available at https://crowdmark.desk.com/customer/portal/articles/1639407-completing-and-submitting-an-assignment.)

Assignments will be handed out and due as follows:
Assignment Number Handed Out Due Hand In Via Markers Solutions
Fri., Jan. 11 Fri., Jan. 25, 6pm CrowdMark Q1: Vedat
Q2: Aseem
Q3: Zhengkun
Q4: Tiasa
Q5: Azin
Q6: Akshay
Q7: Hong
See "a1-solutions.pdf" on Learn, under "Assignment Solutions".
Fri., Jan. 25 Fri., Feb. 8, 6pm CrowdMark Q1: Tiasa
Q2: Azin
Q3: Aseem
Q4: Zhengkun
Q5: Stavros
See "a2-solutions.pdf" on Learn, under "Assignment Solutions".
Updated: PDF, LaTeX
Mon., Feb. 11 Fri., Mar. 1, 6pm
Mon., Mar. 4, 6pm
CrowdMark (Q1-4)
and Marmoset (Q5)
Q1: Hong
Q2: Zhengkun
Q3: Vedat
Q4: Aseem
Q5: Stavros
See "a3-solutions.pdf" on Learn, under "Assignment Solutions".
Solution has been corrected yet again (as of March 20, 2019, 9:03am). See Piazza post @515 for details.
Solution has been corrected yet again (as of April 4, 2019, 7:41pm). See Piazza post @515 for details.
PDF, Latex
Fri., Mar. 1 Sun., Mar. 24, 6pm
Mon., Mar. 25, 6pm
CrowdMark Q1: Akshay
Q2: Azin
Q3: Stavros
Q4: Zhengkun
Q5: Aseem
See "a4-solutions.pdf" on Learn, under "Assignment Solutions".
PDF, Latex
Fri., Mar. 22 Sun., Apr. 7, 6pm CrowdMark (Q1-3)
and Marmoset (Q4)
Q1: Stavros
Q2: Aseem
Q3: Zhengkun
Q4: Stavros

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 was marked, you need to submit a written request for remarking to the TA who marked the relevant question. You must make initial contact with the TA within one week from the day your assignment is returned. For complaints about exam marking, you need to submit the written request to your section's instructor.


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).

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:

Finally, you may also enjoy Brian Christian and Tom Griffiths, Algorithms to Live By: The Computer Science of Human Decisions.

Other Information and University Policies


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.


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.