CS 341: Algorithms, Spring 2016
David R. Cheriton School of Computer Science
Contents:
Announcements,
General Info,
Organization,
Lecture Topics,
Assignments,
Resources,
University Policies
(July 8th) Assignment 5 has posted, and it's due on July 22nd at noon.
(June 23rd) Assignment 4 has posted, and it's due on July 8th at noon.
(June 3rd) Assignment 3 has posted, and it's due on June 24th at noon. For submitting the programming question, please read Programming Guidelines.
(May 20th) Assignment 2 has posted, and it's due on June 3rd at noon.
(May 5th) Assignment 1 has posted. Please also read instructions for assignments and mark appeals.
Instructors:
Timothy Chan, DC 2107, x36941, tmchan "at" uwaterloo "dot" ca
Office hours: Wednesday 12:001:20PM, or by appointment
Semih Salihoglu, DC 3351, x37522, semih.salihoglu "at" uwaterloo "dot" ca
Office hours: Tuesday 12PM @DC3351, or by appointment
Time and Place:
 Section 1: Tuesday & Thursday, 1:00 PM  2:20 PM, MC 4040 (Chan)
 Section 2: Tuesday & Thursday, 2:30 PM  3:50 PM, MC 4040 (Chan)
 Section 3: Tuesday & Thursday, 11:30 AM  12:50 PM, MC 1056 (Salihoglu)
TAs:
TA office hours will be announced on piazza. Alternatively you can email for an appointment.

Eddie Cheung. eycheung "at" uwaterloo "dot" ca. Office: DC3594.

Stephanie Lee. s363lee "at" uwaterloo "dot" ca. Office: DC3552.

Vijay Menon. v3menon "at" uwaterloo "dot" ca. Office: DC3129.

Camila Perez. cmperezg "at" uwaterloo "dot" ca. Office: DC2305.

Daniel Recoskie. dprecosk "at" uwaterloo "dot" ca. Office: DC2306A.

Hong Zhou. h76zhou "at" uwaterloo "dot" ca. Office: DC2581.
Credit:
 Assignments 30%  see dates below.
 Midterm 20%  7:00 PM  9:00 PM (Mon), June 20, 2016.
 Final Exam 50%  TBA.
 Week 1: Introduction
Tuesday (May 3): Administrivia, Overview, Divide & Concur Example: Merge Sort. (Semih's slides: pptx, pdf)
Thursday (May 5): Dynamic Programming Example: Max Subarray, Greedy Example: Scheduling. (Semih's slides: pptx, pdf)
 Week 2: Math Review
Tuesday (May 10): Math Review I: Asymptotic Notation & Recurrences 1 (Substitution Method)  CLRS 3.1, 3.2, 4.3.
Thursday (May 12): Math Review 2: Recurrences 2 (Recursiontree & Master theorem)  CLRS 4.44.6.
 Week 3: Divide and Conquer (handout)
Tuesday (May 17): 2D Maxima & Closest Pair (CLRS 33.4; Semih's slides: pptx, pdf).
Thursday (May 19): Integer Multiplication & Strassen's Matrix Multiplication (CLRS 4.2; Divide & Conquer handout 2.1; Semih's slides: pptx, pdf).
 Week 4: Greedy Algorithms
Tuesday (May 24): Greedy 1 (CLRS 16.116.2, Semih's slides: pptx, pdf).
Thursday (May 26): Greedy 2 (CLRS 16.116.2, Semih's slides: pptx, pdf).
 Week 5: Greedy Algorithms and Dynamic Programming
Tuesday (May 31): Greedy 3 (Semih's slides: pptx, pdf).
Thursday (June 2): Dynamic Programming 1 (CLRS 15.115.3, Semih's slides: pptx, pdf).
 Week 6: Dynamic Programming
Tuesday (June 7): Dynamic Programming 2 (CLRS 15.4, 15.5, Semih's slides: pptx, pdf).
Thursday (June 9): Dynamic Programming 3 (CLRS 15.4, 15.5, Semih's slides: pptx, pdf).
 Week 7: Graph Algorithms
Tuesday (June 14): Graph Algorithms 1 (CLRS 22.122.3, Semih's slides: pptx, pdf).
Thursday (June 16): Graph Algorithms 2 (CLRS 22.422.5, Semih's slides: pptx, pdf).
 Week 8: Graph Algorithms
Tuesday (June 21): Graph Algorithms 3 (CLRS 22.422.5, Semih's slides: pptx, pdf).
Thursday (June 23): Graph Algorithms 4 (CLRS 23.123.2, Semih's slides: pptx, pdf).
 Week 9: Graph Algorithms
Tuesday (June 28): Graph Algorithms 5 (CLRS 24.124.3, Semih's slides: pptx, pdf).
Thursday (June 30): Graph Algorithms 6 (CLRS 25.125.2, Semih's slides (updated July 4): pptx, pdf).
 Week 10: Intractability
Tuesday (July 5): Intractability 1 (CLRS 34.134.2, Semih's slides: pptx, pdf).
Thursday (July 7): Intractability 2 (CLRS 34.334.4, Semih's slides: pptx, pdf).
 Week 11: Intractability
Tuesday (July 12): Intractability 3 (Semih's slides: pptx, pdf).
Thursday (July 14): Intractability 4 (Semih's slides: pptx, pdf).
 Week 12
Tuesday (July 19): Undecidability (Semih's slides: pptx, pdf).
Thursday (July 21): Dealing With Intractability & Beyond (Semih's slides: pptx, pdf).
Assignments are due on Fridays at noon. Except for the third assignment, for which you will have three weeks, 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:
 Assignment 1: posted on May 5th, and due on May 20th (12 NN).
 Assignment 2: posted on May 20th, and due on June 3rd (12 NN).
 Assignment 3: posted on June 3rd, and due on June 24th (12 NN).
 Assignment 4: posted on June 23rd, and due on July 8th (12 NN).
 Assignment 5: posted on July 8th, and due on July 22nd (12 NN).
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).
Please write legibly and stable the pages of your solutions securely. Please use a cover page. Put your full name and ID number on this first page. On the top righthand 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 and are to be placed in the CS341 assignment box located on the on the 4th floor of MC, across from the Tutorial Centre.
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).
For assignments, you should first consult the TA who marked the question. Only if the problem is still unresolved should you then bring the case to the instructor's attention.
For the midterm, your appeal should be submitted to the instructor in writing. Note that as a result of closer scrutiny of your work, marks may go up or down.
(No) Late policy:
Late assignments will not be accepted and will be given a mark of zero. (Accidentally placing assignments in the wrong box or just "forgetting" are not considered valid excuses.) 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 problemsolving 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.
Textbook:
[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
(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).
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
 Introduction to algorithms and algorithm analysis: 1, 2
 Order notation: 3
 Recurrences: 4.3, 4.4, 4.5, (4.6)
 FindMinAndMax: 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
 Singlesource shortest paths: 24
 Singlesource shortest paths algorithm for DAGs: 24.2
 Dijkstra's algorithm: 24.3
 Allpairs shortest parts: 25
 FloydWarshall algorithm: 25.2
 Theory of NP Completeness
 Overview: 34
 P: 34.1
 NP: 34.2
 NPcompleteness, NPhardness, and reductions: 34.3
 SAT, 3CNFSAT: 34.4
 clique, vertexcover, Hamiltonian cycle, travelingsalesman, and subsetsum problems: 34.5
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, http://www.math.uwaterloo.ca/navigation/Current/cheating_policy.shtml .
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 .