This course studies the major algorithmic design paradigms and
mathematical tools for analyzing the running times of algorithms and
detecting computational problems for which no efficient deterministic
algorithm. Topics include: basics of analysis of algorithms; general
algorithmic paradigms: (i) divide and conquer; (ii) greedy algorithms;
(iii) dynamic programming; and (iv) graph algorithms; NP-completeness
and its implications; and undecidability.
The course material includes:
Videos of lectures will be available on Learn, and announced on Piazza. The slides of the lectures will be posted here. If you are happy to learn from the videos and/or slides, that’s fine. When you need more details/examples, or if you like a text book format, here are the corresponding sections of the text, CLRS, together with our recommendations for alternative sources available online. For descriptions of the books, see Resources.
| Date | Topics | Slides | CLRS | Other readings (* = highly recommended) |
||
|---|---|---|---|---|---|---|
| Week 1 | L1 | September 7 | Introduction | 1,2 (the convex hull example is in 33.3 but is not required) | *[Skienna] 1 | |
| L2 | Analyzing Algorithms | 2.2, 3 | * [Skienna] 2 | |||
| Week 2 | L3 | September 14 | Reductions and recurrences | PDF, PDF without notes |
4.3, 4.4, 4.5 | * for reductions: [Erickson] 1.1 |
| L4 | Divide and Conquer I | PDF, PDF without notes |
4.1, 33.4 (closest points) | |||
| Week 3 | L5 | September 21 | Divide and Conquer II | PDF, PDF without notes |
4.2 (matrix multiplication) | [DPV] 2 |
| L6 | Greedy algorithms | PDF, PDF without notes |
16.1 (but hard to read) | [Erickson] 4 | ||
| Week 4 | L7 | September 28 | Exchange proofs for greedy algorithms | PDF, PDF without notes |
16.2 mentions knapsack | |
| L8 | Dynamic Programming I | PDF, PDF without notes |
15 (in general) 15.4 (longest common subseq.) | text segmentation: [Erickson] 3.3, 3.4 longest increasing subsequence: [Erickson] 3.6, [DPV] 6.2 |
||
| Week 5 | L9 | October 5 | Dynamic Programming II | PDF, PDF without notes |
edit distance: [Erickson] 3.7, [DPV] 6.3 | |
| L10 | Dynamic Programming III | PDF (+little difference between plain and annotated, so only 1 version) | 15.5 (optimal binary search trees) | optimal binary search trees: [Erickson] 3.9 0-1 knapsack: [DPV] 6.4 |
||
| October 10 | Thanksgiving and reading week | |||||
| Week 6 | L11 | October 19 | Intro to Graph Algorithms | PDF (+) | 22.1, 22.2 | * [Erickson] 5.1 - 5.4 |
| L12 | Depth first search | PDF (+) | 22.3 | [DPV] 3.2
[Erickson] 6 |
||
| Week 7 | L13 | October 26 | Depth first search in directed graphs | 22.4 | [DPV] 3.3 | |
| L14 | Minimum spanning trees | 23 | [DPV] 5.1
[Erickson] 7 |
|||
| Week 8 | L15 | November 2 | Shortest paths | 24.3 (Dijkstra) | [DPV] 4.4
[Erickson] 8 |
|
| L16 | Dynamic Programming for shortest paths | 24.1, 25.2 | [DPV] 6.6
[Erickson] 9 |
|||
| Week 9 | L17 | November 9 | Exhaustive Search Techniques | [DPV] 9.1
[Erickson] 2.1 - 2.3 [Skienna] 7.1, 7.2 |
||
| L18 | Intro to P, reductions | 34.1 | [DPV] 8
[Erickson] 12 |
|||
| Week 10 | L19 | November 16 | NP and NP-completeness | 34.2 | ||
| L20 | NP-completeness II | 34.5 | ||||
| Week 11 | L21 | November 23 | NP-completeness III | 34.3, 34.4 | ||
| L22 | Approximation algorithms | 35.1, 35.2 | [DPV] 9.2 | |||
| Week 12 | L23 | November 30 | Undecidability | |||
| L24 | Bonus Lecture |
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 separate PDF file (multiple pages are allowed) to each question. You may resubmit as often as necessary until the due date. (More detailed CrowdMark information is available at https://crowdmark.com/help/completing-and-submitting-an-assignment/.)
Marmoset will be used for the programming questions, and is available at https://marmoset.student.cs.uwaterloo.ca.
Assignments will be handed out and due as follows (dates are tentative and may change):
| Assignment Number | Date Posted | Due (5pm EDT/EST) | Hand In Via | Markers | Solutions |
|---|---|---|---|---|---|
| 1 PDF, LaTeX |
Wednesday, September 16 | Wednesday, September 23 | CrowdMark | Q1: John Q2: Mohammadali Q3: Cameron |
See A1 solution sketch under "Assignments" in Learn. |
| 2 PDF, LaTeX |
Wednesday, September 23 | Wednesday, September 30 | CrowdMark | Q1: Ankit Q2: Alex |
See A2 solution sketch under "Assignments" in Learn. |
| 3 PDF, LaTeX |
Wednesday, September 30 | Wednesday, October 7 | CrowdMark | Q1: Utsav Q2: Catherine |
See A3 solution sketch under "Assignments" in Learn. |
| 4 PDF, LaTeX |
Wednesday, October 7 | Wednesday, October 21 | CrowdMark | ||
| Programming 1 |
Wednesday, October 7 | Wednesday, October 28 | Marmoset | ||
| 5 PDF, LaTeX |
Wednesday, October 21 | Wednesday, October 28 | CrowdMark | ||
| 6 PDF, LaTeX |
Wednesday, October 28 | Wednesday, November 4 | CrowdMark | ||
| 7 PDF, LaTeX |
Wednesday, November 4 | Wednesday, November 11 | CrowdMark | ||
| Programming 2 PDF, LaTeX |
Wednesday, November 4 | Wednesday, November 18 | Marmoset | ||
| 8 PDF, LaTeX |
Wednesday, November 11 | Wednesday, November 18 | CrowdMark | ||
| 9 PDF, LaTeX |
Wednesday, November 18 | Wednesday, November 25 | CrowdMark | ||
| 10 PDF, LaTeX |
Wednesday, November 25 | Wednesday, December 2 | CrowdMark |
Instructions for Assignments: Your written solutions will be judged not only for correctness but also for the quality of your presentation and explanations. In questions that involve designing an algorithm, (i) describe the main idea first, (ii) present 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). In all assignments, 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.
Collaboration Policy: The work you hand in must be your own. Unless specified otherwise, you can always use any result from the textbook, notes, or previous assignment just by citing it. You may discuss the assignment questions verbally with others, but you should come away from these discussions with no written or electronic records and you must acknowledge the discussion. Acknowledge any sources you have used. Any assistance received (from human or nonhuman sources) that is not given proper citation may be considered a violation of the university policies.
Late Policy: You will be allowed to hand in up to 2 written assignments 48-hours late without penalty.
Any subsequent late assignments will receive a grade of 0.
Since CrowdMark doesn't handle late days, the deadline posted needs
to be set to the late deadline in order to allow late submissions to be graded.
The number of lates used will thus have to be manually calculated.
While we will periodically post our record of the number of lates that you have used,
you are still responsible for keeping track of the lates you have used yourself.
Anything handed in after the late deadline will not be accepted.
Solutions will be posted almost immediately online on Learn.
Programming Questions: There will be 2 programming assignments, where we ask you to code an algorithm. However, this is not a software engineering course. We will not test your code for trivial edge cases (such as the case of empty input), or inputs that do not match our specifications. 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. We will send out detailed instructions about how to submit programming questions.
We will use Piazza for all course announcements and as a forum for students to ask and answer questions. 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 below.
| Instructor | Email (@uwaterloo.ca) |
Office Hours |
|---|---|---|
| Anna Lubiw | alubiw | Mondays 1 PM - 2 PM (starting Sept. 14) https://us02web.zoom.us/j/83121076569?pwd=SFozMkFkY3E2T2FBMXMyTlVzL2ZiZz09 Meeting ID: 831 2107 6569 Passcode: algorithms (with waiting room set up) |
| Arne Storjohann | astorjohann | Tuesdays 1 PM - 2 PM (starting Sept. 15) https://us02web.zoom.us/j/84251942777?pwd=M0JDeXB6T0U4UHZ1dW1xdDYzNENVZz09 Meeting ID: 842 5194 2777 Passcode: 544529 |
| Teaching assistant | Email (@uwaterloo.ca) |
|---|---|
| Aseem Baranwal | arbaranw |
| Stavros Birmpilis | sbirmpil |
| John Bostanci | cbostanc |
| Utsav Tushar Das | utdas |
| Nathan Harms | nharms |
| Vijay Menon | v3menon |
| Mohammadali Niknamian | mniknami |
| Cameron Seth | cjmpseth |
| Catherine St-Pierre | c2stpier |
| Kam Chuen (Alex) Tung | kctung |
| Ankit Vadehra | avadehra |
| Hong Zhou | h76zhou |
| Time (EDT/EST) | Link |
|---|---|
| Mondays 10 PM -- 11 PM | https://us04web.zoom.us/j/77422317597?pwd=MzlHbndhSXdzY1p5UzFNaUhlNVNlQT09 Meeting ID: 774 2231 7597 Passcode: 2Ck7U7 |
| Tuesdays 10 AM -- 11 AM | |
| Wednesdays 10 AM -- 11 AM | |
| Thursdays 3 PM -- 4 PM |
| Instructional support coordinator | Email (@uwaterloo.ca) |
|---|---|
| Caroline Kierstead | caroline.kierstead |
10 written assignments worth 6% each. 2 programming assignments worth 6% each. 12 quizzes worth 0.5% each. A take-home final exam worth 22%. No midterm exam.
Note: If you decide to e-mail the course staff, you must use your uwaterloo Quest e-mail account (WatIAM/Quest userID @uwaterloo.ca); otherwise we cannot verify who you are and are limited on what we can accept and respond to.
| Help Topic | Contact |
|---|---|
| Assignment, Missed Deadline: | We do not accept emailed assignments or more than 2 late assignments. The last files
submitted before the deadline will be marked (submit early and
often, even if not finished). If the deadline is missed due to illness or other valid, verifiable reason, see Missed Work Due To Illness below. |
| Assignment Marking Error: | Re-mark request, due within one week of release of marks on CrowdMark/Marmoset. Contact the TA who marked the specific question and submit a written request. See TAs for contact information. |
| Assignment Recording Error: | Grades will be made available through https://www.student.cs.uwaterloo.ca/~cs341/cgi-bin/displayMarks.cgi. If you notice an error in the recorded value, please contact Caroline Kierstead (CS 341 ISC). |
| Course Website Error: | Email CS341 course account |
| Handouts Error: | Instructors - email or check consulting hours listed at Instructors |
| Enrollment: | If Quest won't let you enroll or switch LEC or TUT sections without a permission/override number: Instructors and course staff are unable to help you—you must see a CS academic advisor. |
| General Course Help: | TA office hours or instructor office hours. |
| Lecture Questions: | TA office hours or instructor office hours. |
| Missed Work Due To Illness/Valid, Verifiable Reason (Assignments, Exams): | Assignments, midterms, final exam: Validation required (see Verification of Illness Services at https://uwaterloo.ca/campus-wellness/health-services/student-medical-clinic but substitute Caroline Kierstead (CS 341 ISC) for references to instructor. Make sure you also read the Math Faculty document on the consequences of submitting a VIF. |
| AccessAbility Services (AAS) exam accommodation forms (request to write at AAS): | Submit to AAS at least 3 weeks before exam |
If you are person who likes a more detailed text book format, here are our recommendations for sources available online.
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:
MOSS (Measure of Software Similarities) is used in this course as a means of comparing students' assignments to ensure academic integrity. We will report suspicious activity, and penalties for plagiarism/cheating are severe. Please read the available information about academic integrity very carefully.
Discipline cases involving any automated marking system such as Marmoset include, but are not limited to, printing or returning values in order to match expected test results rather than making an actual reasonable attempt to solve the problem as required in the assignment question specification.