David R. Cheriton School of Computer Science
Anna Lubiw, DC 2334, x34449, alubiw "at" uwaterloo.ca
Office hours: Monday 3-4pm, Tuesday 4-5pm, DC2334.
Bin Ma, DC 3345, x32747, binma "at" uwaterloo.ca
Office hours: Thursday 3-4pm, DC3345.
Eugene Zima, DC 2127, ezima "at" uwaterloo.ca
Office hours: Tuesday 2:30-4pm, DC2127.
Time and Place:
All Office hours:
For week-to-week changes, see Piazza.
|Monday||3-4 pm||Anna Lubiw||DC 2334|
|Tuesday||2:30-4 pm||Eugene Zima||DC 2127|
|Tuesday||4-5 pm||Anna Lubiw||DC 2334|
|Wednesday||10-11 am||TAs||DC 2136B (CS advising office)|
|Wednesday||3-4 pm||TAs||DC 3323|
|Thursday||3-4 pm||Bin Ma||DC 3345|
|Friday||11 am - noon||TAs||DC 2136B (CS advising office)|
Collaboration policy: The work you hand in must be your own. The value of the assignment is in doing it yourself (as you must do on tests and exams). Acknowledge any sources (human or non-human) you have used. 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. If you use an electronic source, again, read it, then close it, then compose your solution and acknowledge your source. Write your solutions in your own words, from your own head. Any assistance received (from human or nonhuman sources) that is not given proper citation may be considered a violation of the university policies.
Submission: Assignments will be submitted as pdf files (each question as a separate pdf).
Type your assignments or write legibly. We are using Crowdmark to submit assignments this term. Before the submission deadline (usually the weekend before the deadline), we will send a submission link to your uwaterloo email and make an announcement on piazza. If you didn't get the link or have any question about the submission, you can contact Hong Zhou (firstname.lastname@example.org). If you need any help for submitting via Crowdmark, you can find instructions here.
Programming: Some of the assignments will contain programming questions, for which we will provide detailed instructions on how to submit your programs.
Late Policy: Assignments are due at 7 PM on Wednesdays (except A4 is delayed to Thursday because of reading days). To give you some flexibility we will allow up to two late submissions on assignments and up to one late submission on programming. You cannot mix the two. A "late submission" means handing in by 7 PM on Friday instead on Wednesday.
Mark Appeals: 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.
Assignments and Due Dates:
Note: we have separated the programming questions out of the assignments since they have 2-week deadlines and will be handed in differently.
|A1||tex||Mon. Sep. 11||Wed. Sep. 20||10|
|A2||tex||Mon. Sep. 18||Wed. Sep. 27||6|
|P1||Mon. Sep. 18||Wed. Oct. 4||8|
|A3||tex||Mon. Sep. 25||Wed. Oct. 4||6|
|A4||tex||Mon. Oct. 2||Thurs. Oct. 12||10|
|A5||tex||Tues. Oct. 10||Wed. Oct. 18||6|
|P2||Tues. Oct. 10||Wed. Nov. 1||8|
|A6||tex||Mon. Oct. 16||Wed. Nov. 1||6|
|A7||Mon. Oct. 30||Wed. Nov. 8||10|
|A8||Mon. Nov. 6||Wed. Nov. 15||6|
|P3||Mon. Nov. 6||Wed. Nov. 22||8|
|A9||Mon. Nov. 13||Wed. Nov. 22||6|
|A10||Mon. Nov. 20||Wed. Nov. 29||10|
Note: Lecture notes for Sections 3 and 4 (Prof. Ma and Prof. Zima's sections) are downloadable from LEARN. Please feel free to share a copy with another student who does not have LEARN access.
|L01||Th Sep  7||Introduction||L1||[CLRS Ch. 1] [S Ch. 1]|
|L02||Tu Sep  12||Analyzing algorithms: models of computation, asymototic analysis, order notation||L2||[CLRS 2.2, Ch. 3] [S Ch. 2]|
|L03||Th Sep  14||Reductions. Recurrences: Reducing 3-SUM to 2-SUM. Solving recurrences||L3||recurrences [CLRS 4.3], [DPV 2.2]|
|L04||Tu Sep  19||Master Theorem and Divide and Conquer: counting inversions||L4||inversions [KT 5.3]|
|L05||Th Sep  21||Divide and Conquer: closest pair of points, multiplying numbers and matrices||L5||closest pair [KT 5.4], [CLRS 33.4]. integer mult. [DPV 2.1], [KT 5.5]. matrix mult. [CLRS 4.2].|
|L06||Tu Sep  26||Greedy Algorithms: making change, activity selection, scheduling to minimize lateness||L6||[CLRS 16.1] but not too readable. [KT 4.1]|
|L07||Th Sep  28||Greedy Algorithms: more examples including fractional knapsack||L7|
|L08||Tu Oct  3||Dynamic Programming: Weighted interval scheduling, Max. Common Subsequence||L8||general refs.: [CLRS Ch. 15] [KT Ch. 6] [DPV Ch. 6]. weighted interval scheduling [KT 6.1]|
|L09||Th Oct  5||Dynamic Programming 2: Edit distance, making change, optimum binary subtrees||L9||general refs.: [CLRS Ch. 15] [KT Ch. 6] [DPV Ch. 6].|
|L10||Th Oct  12||Dynamic Programming 3: Knapsack, Subset Sum, Chain Matrix Multiplication||L10||general refs.: [CLRS Ch. 15] [KT Ch. 6] [DPV Ch. 6].|
|L11||Tu Oct  17||Graph Algorithms and BFS: definitions, storage of graphs, Breadth First Search||L11||Graph definitions: [CLRS, Appendix B.4]. BFS: [CLRS 22.2], [S 5.6], or see Erickson's notes|
|L12||Th Oct  19||Depth First Search (undirected): depth first search, 2-connected components||L12||[CLRS 22.3, 2-connected components is Problem 22-2], [S 5.8, 5.9]|
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. [Check https://uwaterloo.ca/academic-integrity/ for more information.]
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. When in doubt please be certain to contact the department's administrative assistant who will provide further assistance.
Discipline: A student is expected to know what constitutes academic integrity [check https://uwaterloo.ca/academic-integrity/] to avoid committing an academic offence, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (e.g., plagiarism, cheating) or about 'rules' for group work/collaboration should seek guidance from the course instructor, academic advisor, or the undergraduate Associate Dean. For information on categories of offences and types of penalties, students should refer to Policy 71, Student Discipline. For typical penalties check Guidelines for the Assessment of Penalties.
Appeals: A decision made or penalty imposed under Policy 70 (Student Petitions and Grievances) (other than a petition) or Policy 71 (Student Discipline) may be appealed if there is a ground. A student who believes he/she has a ground for an appeal should refer to Policy 72, Student Appeals.
Note for Students with Disabilities: AccessAbility Services, located in Needles Hall, Room 1401, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with AccessAbility Services at the beginning of each academic term.
Intellectual Property: Students should be aware that this course contains the intellectual property of their instructor, TA, and/or the University of Waterloo. Intellectual property includes items such as:
Course materials and the intellectual property contained therein, are used to enhance a student's educational experience. However, sharing this intellectual property without the intellectual property owner's permission is a violation of intellectual property rights. For this reason, it is necessary to ask the instructor, TA and/or the University of Waterloo for permission before uploading and sharing the intellectual property of others online (e.g., to an online repository).
Permission from an instructor, TA or the University is also necessary before sharing the intellectual property of others from completed courses with students taking the same/similar courses in subsequent terms/years. In many cases, instructors might be happy to allow distribution of certain materials. However, doing so without expressed permission is considered a violation of intellectual property rights.
Please alert the instructor if you become aware of intellectual property belonging to others (past or present) circulating, either through the student body or online. The intellectual property rights owner deserves to know (and may have already given their consent).