|Eric Blaisfirstname.lastname@example.org||DC 3122||Wednesdays 11:30am-12:30pm|
|Anna Lubiwemail@example.com||DC 2334||Tuesdays 3:00pm-4:00pm|
|Instructional support coordinator||Office|
|Caroline Kiersteadfirstname.lastname@example.org||DC 3127 x36226|
|LEC 001||08:30-09:50 MW||MC 2017||Anna Lubiw|
|LEC 002||11:30-12:50 TTh||PHY 145||Eric Blais|
|LEC 003||10:00-11:20 TTh||PHY 145||Eric Blais|
Tutorials start the week of September 13.
|101||8:30-9:20 F||MC 2034|
|102||9:30-10:20 F||RCH 207|
|104||3:30-4:20 F||PHY 313|
During the lecture period (lectures end December 3rd):
|Midterm Exam (Oct. 22, 7-8:50pm, M3 1006, MC 1085)||25|
|Final Exam (Dec. 18, 12:30-3pm, PAC 1, 2, 3)||40|
Note: If you decide to e-mail the course staff, you must use your uwaterloo Quest e-mail account (WatIAM/Quest userID @edu.uwaterloo.ca); otherwise we cannot verify who you are and are limited on what we can accept and respond to.
|Assignment, Missed Deadline:||We do not accept late or emailed 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 MarkUs/CrowdMark/Marmoset. Contact the TA who marked the specific question and submit a written request. See TAs for contact information.|
|Course Website Error:||Email CS341 course account|
|Handouts Error:||Instructors - email or check consulting hours listed at|
|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.|
|Exam Seat (Midterms & Final):||Assigned seating. See https://odyssey.uwaterloo.ca/teaching/schedule.|
|General Course Help:||TA office hours or instructor office hours.|
|Lecture Questions:||TA office hours or instructor office hours.|
|Midterm Remarks:||For complaints about exam marking, you need to submit the written request to your section's instructor.|
|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|
We are not following the text exactly. Lecture notes are included below, along with references to the corresponding sections in the course textbook.
|Lecture||Dates||Topics||CLRS Section||Notes (Lubiw)||Notes (Blais)|
|2||Sept 9/10||Analyzing algorithms||3|
|3||Sept 11/12||Reductions and recurrences||4.4-4.5|
|4||Sept 16/17||Divide and conquer I||4|
|5||Sept 18/19||Divide and conquer II||4, 33.4|
|6||Sept 23/24||Greedy algorithms||16|
|7||Sept 25/26||Exchange proofs for greedy algorithms||16|
|8||Sept 30/Oct 1||Dynamic programming I||15|
|9||Oct 2/3||Dynamic programming II||15|
|10||Oct 7/8||Dynamic programming III||15|
|11||Oct 9/10||Intro to graph algorithms||22|
|12||Oct 21/22||Depth-first search||22|
|13||Oct 23/24||Depth-first search in directed graphs||22|
|14||Oct 28/29||Minimum spanning trees||23|
|15||Oct 30/31||Shortest paths||24|
|16||Nov 4/5||Dynamic programming for shortest paths||24, 25|
|17||Nov 6/7||Exhaustive search techniques|
|18||Nov 11/12||Introduction to P, reductions||34|
|19||Nov 13/14||NP and NP-completeness||34|
|20||Nov 18/19||NP-completeness II||34|
|21||Nov 20/21||NP-completness III||34|
|22||Nov 25/26||Approximation algorithms||35|
|24||Dec 2/3||Bonus lecture|
When the MarkUs instance is ready, the assignment will be visible in MarkUs and an announcement will be made on Piazza. 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.
Assignments will be handed out and due as follows (dates are tentative and may change):
|Assignment Number||Handed Out||Due||Hand In Via||Markers||Solutions|
PDF, LaTeX template
|Sept 11||Sept 18, 5pm||MarkUs||Q1: Shubhankar
|See A1 solutions under "Assignments" in Learn.|
PDF, LaTeX template
|Sept 18||Sept 25, 5pm||MarkUs||Q1: Vijay
PDF, LaTeX template
|Sept 25||Oct 2, 5pm||MarkUs||Q1: Alex
PDF, LaTeX template
|Oct 2||Oct 9, 5pm||MarkUs||Q1: Sachin
PDF, LaTeX template
|Oct 9||Oct 30, 5pm||MarkUs||Q1: Aseem|
|Programming 1 PDF||Oct 9||Oct 30, 5pm||MarkUs||Q1: Shubhankar|
|6||Oct 30||Nov 6, 5pm|
|7||Nov 6||Nov 13, 5pm|
|Programming 2||Nov 6||Nov 20, 5pm|
|8||Nov 13||Nov 20, 5pm|
|9||Nov 20||Nov 27, 5pm|
Instructions for Assignments: You have three grace credits that will let you hand in up to three assignments, each up to a maximum of 48 hours late, without penalty. You may use no more than one grace credit per assignment. Once your grace credits are used up, any late assignment will receive a grade of 0.
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).
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.
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:
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 https://www.student.cs.uwaterloo.ca/~cs341/cgi-bin/displayMarks.cgi.
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.
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 or MarkUs 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.