CS 341: Algorithms, Winter 2017
David R. Cheriton School of Computer Science
- Assignments due dates have been updated
- Assignment 4 is now available. It is due March 14. (See assignments section)
- Sample midterm is available (See credit section)
- Yaoliang's slides for lecture 11 have been posted
- Yaoliang's slides for lecture 10 have been updated
- Semih's slides for lecture 13 and 14 have been updated
- Lecture topics for week 6 have been posted
- Semih's slides for lecture 13 and 14 are now available
- Yaoliang's slides for week 6 have been posted
- Lecture topics for week 6 have been posted
- Semih's slides for lecture 11 and 12 are now available
- tex file for assignment 3 is now available
- Assignment 3 is now available. It is due Feb 17. (See assignments section)
- Yaoliang's slides for weeks 4 and 5 have been posted
- Lecture topics for week 5 have been posted
- Semih's slides for lecture 10 are now available
- Assignment 2 is now available. It is due Feb 3
- Semih's slides for lecture 6 have been updated
- Lecture topics for week 4 have been posted
Yaoliang's slides for week 3 are now available.
- TA office hours have been updated.
- Corrected version of slide 77 has been posted (Doug)
- Yaoliang's slides for week 2 are now available
- Lecture topics for week 3 have been posted
- Semih's slides for week 3 are now available
Lecture topics for week 2 have been posted.
LaTeX file for assignment 1 is available.(See assignments section)
Assignment 1 is now available. It is due Jan 20. (See assignments section)
Piazza will be used for all
Douglas Stinson, DC 3522, x35590, dstinson "at" uwaterloo.ca
Office hours: Thursdays, DC 3522, 01:30-02:30 p.m.
Semih Salihoglu, DC 3351, x37522, semih.salihoglu "at" uwaterloo.ca
Office hours: Wednesdays, DC 3351, 11:00-12:00 p.m.
Yaoliang Yu, DC 3602, yaoliang.yu "at" uwaterloo.ca
Office hours: Tuesdays, DC 3602, 10:00-10:00 a.m.
Time and Place:
- Section 1: Tuesday & Thursday, 02:30 - 03:50 p.m., MC 2034, (Semih)
- Section 2: Tuesday & Thursday, 10:00 - 11:20 a.m., RCH 207, (Douglas)
- Section 3: Tuesday & Thursday, 04:00 - 05:20 p.m., MC 2034, (Semih)
- Section 4: Tuesday & Thursday, 08:30 - 09:50 a.m., RCH 207, (Douglas)
- Section 5: Tuesday & Thursday, 08:30 - 09:50 a.m., MC 4040, (Yaoliang)
- Aayush Rajasekaran (arajasekaran "at" uwaterloo.ca)
- Dimitrios Skrepetos (dskrepet "at" uwaterloo.ca)
- Jian Li (j493li "at" uwaterloo.ca)
- Jose Serna (jserna "at" uwaterloo.ca)
- Shayan Hassantabar (ss3hassa "at" uwaterloo.ca)
- Shikha Mahajan (s7mahaja "at" uwaterloo.ca)
- Woojung Kim (w3kim "at" uwaterloo.ca)
TA Office hours will be in DC2102 the following dates:
Tuesday 3:00 - 4:00 p.m.
Wednesday 3:00 - 4:00 p.m.
Thursday 2:00 - 3:00 p.m.
Douglas' slides: 1up, 2up, slide 77
Semihs' slides: Will be posted weekly (see below)
Yaoliangs' slides: Will be posted weekly (see below)
- Week 1: Introduction
Tuesday (Jan 3): Administrivia, Overview, Divide & Concur Example: Merge Sort. (Semih's slides: pptx, pdf. Yaoliang's slides: pdf)
Thursday (Jan 5): Asymptotic Notation: For reading Assign CLRS 3.1, 3.2. (Semih's slides: pptx, pdf. Yaoliang's slides: pdf)
- Week 2: Assymptotic Notation and Recurrences
Tuesday (Jan 10): Asymptotic Notation and Summations: Reading CLRS 3.1, 3.2. (Yaoliang's slides: pdf)
Thursday (Jan 12): Recurrences & Master Theorem: Reading 4.3-4.5 (optional 4.6). (Yaoliang's slides: pdf)
- Week 3: Divide & Conquer
Tuesday (Jan 17): Divide & Conquer 1: CLRS 3.2, 33.4, D&C handout 2.1. (Semih's slides: pptx, Yaoliang's slides: pdf)
Thursday (Jan 19): Divide & Conquer 2: CLRS 3.2, 33.4, D&C handout 2.1. (Semih's slides: pptx,Yaoliang's slides: pdf)
- Week 4: Greedy Algorithms
Tuesday (Jan 24): Greedy Algorithms 1: CLRS 16.1-16.2. Semih and Doug will finish Divide & Conquer (Semih's slides: pptx, Yaoliang's slides: pdf)
Thursday (Jan 26): Greedy Algorithms 2: CLRS 16.1-16.2. (Semih's slides: pptx,Yaoliang's slides: pdf)
- Week 5: Greedy Algorithms
Tuesday (Jan 31): Greedy Algorithms 3: CLRS 16.1-16.2. (Semih's slides: pptx, Yaoliang's slides: pdf)
Thursday (Feb 2): Greedy Algorithms 4: CLRS 16.1-16.2. (Semih's slides: pptx, Yaoliang's slides: pdf)
- Week 6: Dinamic Programming
Tuesday (Feb 7): Dynamic Programming 1: (CLRS 15.1-15.3). Semih will finish Stable Marriage. (Semih's slides: pptx, Yaoliang's slides: pdf)
Tuesday (Feb 9): Dynamic Programming 2: (CLRS 15.4-15.5). (Semih's slides: pptx, Yaoliang's slides: pdf)
- Week 7: Dinamic Programming - Graph Algorithms
Tuesday (Feb 14): Dynamic Programming 3. Doug will start with Graph algorithms. (Semih's slides: pptx, Yaoliang's slides: pdf)
Tuesday (Feb 16): Graph Algorithms 1: CLRS 22.1-22.3. Semih will take the first half to finish Dynamic Programming. (Semih's slides: pptx)
Assignments are due at noon. You will have two weeks to complete the assignments. Some of the assignments will contain programming questions, for which we will provide detailed instructions on how to submit your programs. The assignment due dates are as follows:
Regarding written work: Your solutions will be judged not only for correctness but also for the quality of your presentation and explanations (justifications are implicitly required in most questions). Ensure that your solutions are complete and mathematically precise, and at the same time, easy to understand and to the point. In questions that involve designing an algorithm, (i) describe the main idea first if that is helpful, (ii) present a 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).
- Assignment 1 (pdf, tex): due Friday Jan. 20
- Assignment 2 (pdf, tex): due Friday Feb. 3
- Assignment 3 (pdf, tex): due Friday Feb. 17
- Assignment 4 (pdf, tex): due Tuesday March 14
- Assignment 5: due Monday April 3
Assignments will be submitted as pdf files in LEARN. In LEARN you will upload your assignments to the specific dropbox for the assignment. Please type your assignments or write legibly. Please use a cover page. Put your full name and ID number on this first page. On the top right-hand corner of the first page, put the first two characters of your last name in big capital letters followed by the section number for the section in which you want to pick up your assignment. For example: if John Doe is attending Section 2, he would write "DO 2" (not "JD 2").
As per the collaboration policy, you must indicate on your assignments any assistance you received.
Assignments are due at noon. So the dropbox on LEARN will close at that time.
All mark appeals (for assignments and midterm) must be made within two weeks of the date of the return (if you pick up your assignment/exam late, your appeal period does not lengthen).
Your appeal should be submitted to the TA who marked the question in writing. Only if the problem is still unresolved should you then bring the case to the instructor's attention
(No) Late policy:
Late assignments will not be accepted and will be given a mark of zero. In case of genuinely extenuating circumstances such as serious illness, please let us know as soon as possible.
While you are not permitted to receive aid from other people, on many occasions, it is useful to ask others (TAs, the instructor, and other students) for hints generally about problem-solving strategies and presentation. This should be limited to the type of advice you get from the instructor and TAs during their office hours. Such activity is both acceptable and encouraged, but you must indicate on your assignments any assistance you receive. Any assistance received (from human or nonhuman sources) that is not given proper citation may be considered a violation of the university policies.
Remember that, you are responsible for understanding and being able to explain all of the statements in your homeworks and exam solutions. Most importantly, the solutions must be written up independently of the other students.
[CLRS] Cormen, Leiserson, Rivest, and Stein,
Introduction to Algorithms (3rd ed.), MIT Press,
2009 (QA76.6 .C662 2009).
CLRS is available in the Davis Centre Library Reserves, as well as the following textbooks:
- [DPV] Dasgupta, Papadimitriou, and Vazirani, Algorithms (QA9.58 .D37 2008);
- [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).
Suggested Readings from CLRS
Below is a list of relevant sections for some of the problems and topics covered in lectures. Less immediately applicable readings are given in parentheses.
- Introduction to algorithms and algorithm analysis: 1, 2
- Order notation: 3
- Recurrences: 4.3, 4.4, 4.5, (4.6)
- Find-Min-And-Max: Problem: 9.1
- Divide and Conquer
- Overview: Section 4
- Matrix Multiplication: 4.2
- Closest pair problem: 33.4
- Selection problem: 9.2, 9.3
- Greedy Algorithms
- Dynamic Programming
- Overview: 15
- Memoization: 15.3
- Longest common subsequence: 15.4
- Graph Algorithms
- Overview of graphs: B.4
- Graph representations: 22.1
- BFS: 22.2
- DFS: 22.3
- Topological Sort: 22.4
- Strongly Connected Components: 22.5
- Minimum spanning trees: 23
- Kruskal's algorithm and Prim's algorithm: 23.2
- Single-source shortest paths: 24
- Single-source shortest paths algorithm for DAGs: 24.2
- Dijkstra's algorithm: 24.3
- All-pairs shortest parts: 25
- Floyd-Warshall algorithm: 25.2
- Theory of NP Completeness
- Overview: 34
- P: 34.1
- NP: 34.2
- NP-completeness, NP-hardness, and reductions: 34.3
- SAT, 3-CNF-SAT: 34.4
- clique, vertex-cover, Hamiltonian cycle, traveling-salesman, and subset-sum problems: 34.5
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, http://www.math.uwaterloo.ca/navigation/Current/cheating_policy.shtml .
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 .