CS 341: Algorithms, Winter 2015
David R. Cheriton School of Computer Science
Contents:
Announcements,
General Info,
Organization,
Outline,
Assignments,
Resources,
University Policies
Course Evaluations:
Please fill out a course evaluation at evaluate.uwaterloo.ca. Surveys for CS 341 will be open from Sunday March 22 (23:59) to Monday April 06 (23:59).
We will not use the newsgroup
uw.cs.cs341. Instead we will use
Piazza for all
course discussion and announcements.
Please be familiar with the general policies and programming guidelines:
Instructors:
Timothy Chan, DC 2107, x36941, tmchan "at" uwaterloo "dot" ca
Office hours: Friday 3:00 PM  4:00 PM, or by appointment
Doug Stinson, DC 3522, x35590, dstinson "at" uwaterloo "dot" ca
Office hours: Wednesday 2:30 PM  3:30 PM, or by appointment
Andrew Arnold, DC 2302E, x34474, a4arnold "at" uwaterloo "dot" ca
Office hours: Monday 12:00 PM  1:00 PM, or by appointment
**Office hours for Monday, April 6 rescheduled to 12pm Thursday, April 2.
Time and Place:
 Section 1: Wednesdays & Fridays, 8:30 AM  9:50 AM, MC 2038 (Chan)
 Section 2: Wednesdays & Fridays, 11:30 AM  12:50 PM, RCH 309 (Chan)
 Section 3: Wednesdays & Fridays, 8:30 AM  9:50 AM, DWE 2527 (Arnold)
 Section 4: Wednesdays & Fridays, 4:00 PM  5:20 PM, MC 1056 (Stinson)
TAs:
TA office hours will be announced on piazza. Alternatively you can email for an appointment.

Zachary Frenette. zfrenett "at" uwaterloo "dot" ca. Office: DC 2503.

Honghao Fu. h7fu "at" uwaterloo "dot" ca. Office: QNC 3321.

Oliver Grant. odlgrant "at" uwaterloo "dot" ca. Office: DC 2569.

Neeraj Kumar. n26kumar "at" uwaterloo "dot" ca. Office: DC 2531.

Ankit Pat. apat "at" uwaterloo "dot" ca. Office: DC 3562.

Dimitrios Skrepetos. dskrepet "at" uwaterloo "dot" ca. Office: DC 2505.
Credit:
 Assignments 30%  see dates below.
 Midterm 20%  Thursday, Feb 26, 2015, 7 PM  8:50 PM,
You will be assigned to a room for the midterm by last name as follows:
 MC 2034: AC
 MC 2038: DI
 MC 4020: JL
 MC 4021: MR
 MC 4059: SWa
 MC 4061: WeZ
 Final Exam 50%  Saturday, April 18, 2015, 9 AM  11:30 AM. PAC 4, 5, 6.
This is a rough outline of the course. It may differ slightly from section to section.
 Introduction
 Lecture 01  20150107: Maximum, MaxandMin, 3SUM, introduction to algorithm analysis.
 Lecture 02  20150109: Asymptotic (order) notation, summation formulas.
 Lecture 03  20150114: Growth of functions, loop analysis, recurrences.
 Lecture 04  20150116: Solving recurrences, recurrence trees, the Master Theorem, the guessandcheck method.
 Divide and Conquer
 Lecture 05  20150121: Divide and conquer algorithms. The maxima problem.
 Lecture 06  20150123: The closestpair problem and Shamos' algorithm. Integer multiplication and Karatsuba's algorithm.
 Lecture 07  20150128: Matrix multiplication and Strassen's algorithm.
 Lecture 08  20150130: The selection problem. Randomized and deterministic lineartime algorithms for selection.
 Greedy Algorithms
 Lecture 09  20150204: Interval selection. Interval colouring
 Lecture 10  20150206: Fractional knapsack problem.
 Lecture 11  20150211: Stable marriage problem. Coin changing problem.
 Dynamic Programming
 Lecture 12  20150213: The combinatorial choose function OR the Fibonacci sequence. A DP solution to the coin changing problem. Solving DP by memoization.
 Lecture 13  20150225: Longestcommon subsequence. The 01 Knapsack problem. Minimumlength triangulation. Solving DP via memoization
 Graph Algorithms
 Lecture 14  20150227: Overview of graphs. Adjacency matrix and adjacency list representations.
 Lecture 15  20150304: Breadthfirst search (BFS) and depthfirst search (DFS).
 Lecture 16  20150306: Applications of BFS and DFS. Bipartiteness. Shortest unweighted path from a fixed vertex. Topological sort.
 Lecture 17  20150311: Sharir's algorithm for strongly connected components. Minimum spanning trees (MSTs) and Kruskal's algorithm.
 Lecture 18  20150313: Prim's algorithm for MST.
 Lecture 19  20150318: Singlesource shortest paths. An algorithm for singlesource shortest paths in DAGs. Dijkstra's algorithm.
 Lecture 20  20150320: 3 dynamicprogramming methods for computing allpairs shortest paths, including the FloydWarshall algorithm.
 NPCompleteness
 Lecture 21  20150325: Decision problems. P and NP decision problem classes. Certificates and verification. P vs NP conjecture.
 Lecture 22  20150327: NPComplete, NPHard classes. Vertex cover. Satisfiability (SAT). Cook's Theorem. Polynomialtime reductions.
 Lecture 23  20150401: 3CNFSatisfiability (3SAT) problem. Independent Set problem. The clique problem.
 Lecture 24  20150406: Undecidability and the halting problem.
Assignments may have a programming question in addition to written work.
Please familiarize yourself with the course policies and the programming guidelines.
Where to get your marked assignment
Assignments will be handed back in the section you wrote down on your assignment. You will also be able to collect your assignments during the office hours of the lecturer of your registerd section. If you did not write down a section
How to appeal marks
After assignments have been handed back to students in class, you have two weeks to appeal you mark. You must first consult the TA who marked the question. (see Piazza postings for whom). Only if the problem is still unresolved should you then bring the case to the instructor's attention.
How to get assignment solutions
In order to access solutions, you need a user name and password. These will be made available to students via piazza.
Tentative dates:
 Assignment 1  Available Wednesday, January 14. Due Tuesday, January 27, 4 PM.
Assignment 1 solutions
 Assignment 2  Available Wednesday, January 28. Due Tuesday, February 10, 4 PM.
Assignment 2 solutions
 Assignment 3  Available Friday, February 13. Due Tuesday, March 3, 4 PM. Please read the updated programming guidelines.
Assignment 3 solutions
 Assignment 4  Available Wednesday, March 4. (Assignment updated Mar 12). Due Tuesday, March 17, 4 PM.
Assignment 4 solutions
 Assignment 5  Available Wednesday, March 17. Due
Tuesday, March 31 Thursday, Apr 2, 4 PM. Lates accepted until Monday, Apr 6, 4pm.
Assignment 5 solutions
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
Lecture Slides and Notes
These lectures slides will be used in section 4 (Stinson).
 Course Info
 Introduction
 Divide and Conquer Algorithms
 Greedy Algorithms
 Dynamic Programming
 Graph Algorithms
 NPCompleteness and Undecidability
Other links of interest
 20150107: A proof that MINMAX requires 3n/22 comparisions: link.
 20150109: A probabilistic O(n^2 (loglog n)^2/ log n) 3SUM algorithm: link.
 20150130: The BlumFloydPrattRivestTarjan selection algorithm: link. This is behind a paywall. You can access it via internet at the University of Waterloo.
 20150225: Notes on minlength triangulation: link.
 20150401: tree of NPcomplete problems connected by polynomial time reductions: link (Source).
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 .