Office hours: Held at the times and locations indicated in the table below. Vassos's office hours start on Week 1; TAs' office hours start on Week 2.
| Day | Time | Place | Person |
| Mon |
4-5 | IA 4024 | Vassos |
| 5-6 | IA 3004 |
Ali | |
| Tue |
11-12 | IA 3004 | Yulong |
| 4-5 | IA 3004 | Lingfei | |
| Wed |
3:30-4:30 | IA 4024 |
Vassos |
| 5:30-6:30 | IA 3004 | Christopher |
Course web page: http://www.cs.toronto.edu/~vassos/teaching/c73/
Prerequisites: CSCB63, STAB52, and enrollment in a computer science subject POSt (or CGPA of 3.5 or higher).
Textbooks:
Kleinberg
and Tardos. Algorithm Design. Addison Wesley 2006.
Dasgupta, Papadimitriou, and Vazirani. Algorithms. McGraw-Hill
2006.
Both of these textbooks are excellent resources with complementary
strengths. You do not need to own both.
Tentative weekly schedule (check regularly as it may change):
| Week |
Lecture
topics |
Study materials | Tutorials
|
Assignments
& tests |
| 1 (Sep 1) |
Greedy algorithms Mon: Labour Day (no class) Wed: Course goals and logistics. Interval scheduling |
KT* 4.1, notes (pp. 1-2) |
No tutorial this week | Wed: A1 posted; advice on presenting algorithms and proofs |
| 2 (Sep 8) | Greedy algorithms, cont'd Mon: Minimum lateness scheduling Wed: Dijkstra's single-source shortest paths algorithm; fractional knapsack |
KT 4.2, notes (pp. 3-5) KT 4.4, DPV 4.3-4.4, notes (Dijkstra), notes (fractional knapsack) |
Practice with greedy algorithms --- Slides | Wed: A1 due, A2 posted |
| 3 (Sep 15) |
Greedy algorithms, cont'd; Divide & conquer (D&C) algorithms Mon: Huffman codes Wed: D&C recurrences; Karatsuba's integer multiplication; Strassen's matrix multiplication |
KT 4.8, DPV 5.2, notes (Huffman), slides (Huffman) KT 5.1-5.2, DPV 2.2, notes ("Master Theorem"), slides (Karatsuba); KT 5.5, DPV 2.1; DPV 2.5 |
Practice with greedy algorithms |
Wed: A2 due, A3 posted |
| 4 (Sep 22) |
D&C algorithms, cont'd Mon: Closest pair of points Wed: Order statistics Optional material: Fast Fourier Transform |
KT 5.4, pseudocode KT 13.5, DPV 2.4, notes Complex numbers review, video (on Quercus), DPV 2.6, KT 5.6 |
Practice with D&C algorithms | Wed: A3 due, A4 posted |
| 5 (Sep 29) |
Dynamic programming (DP) Mon: Longest increasing subsequence Wed: Weighted interval scheduling; optimal sequence alignment |
DPV 6.2, notes KT 6.1; KT 6.6, DPV 6.3, slides |
Practice with DP algorithms | Wed: A4 due, A5 posted |
| 6 (Oct 6) |
DP algorithms, cont'd Mon: Optimal binary search trees Wed: Knapsack & susbset sum; optimal fingering of music scores; DP and recursion, memoisation |
notes KT 6.4, DPV 6.4 |
TBA |
Wed: A5 due, A6 posted |
| 7 (Oct 13) |
DP algorithms, cont'd Mon: Thanksgiving (no class) Wed: Bellman-Ford algorithm (single-source shortest paths) and Floyd-Warshall algorithm (all-pairs shortest paths) Optional material: Johnson's algorithm |
KT 6.8; notes (negative weight egdes), DPV 6.6. notes (Johnson's algorithm) |
TBA | |
| 8 (Oct 20) |
Maximum flow & applications Mon: Max flow problem, Ford-Fulkerson algorithm Wed: Analysis of Ford-Fulkerson algorithm, max-flow min-cut theorem |
KT 7.1-7.2, DPV 7.2, slides KT 7.2-7.3, DPV 7.2, slides, notes (augmenting path choice), notes (flow theorem) |
TBA | Wed: A6 due, A7 posted |
| (Oct 28) | Reading Week (no classes, tutorials, or office hours) | |||
| 9 (Nov 3) |
Maximum flow &applications, cont'd Mon: Bipartite graph matching Wed: Bipartite graph vertex cover; disjoint paths in directed and undirected graphs Optional material: Menger's theorem |
KT 7.5, DPV 7.3, slides KT 7.6, notes notes (Menger's theorem) |
Practice with max flow and applications | |
| 10 (Nov 10) |
Linear Programming (LP) Mon: Motivation, examples, the geometry of LP Wed: LP algorithms, reductions to LP; integer LPs (ILPs), reductions to ILP |
DPV 7.1, slides DPV 7.6, notes (LPs for shortest paths) |
No tutorial this week | Wed: A7 due, A8 posted |
| 11 (Nov 17) |
Approximation algorithms Mon: Approximate vertex cover Wed: Approximate set cover; minimum makespan |
KT 11.6, DPV 9.2.1 KT 11.3, DPV 5.4; KT 11.1, slides |
Practice with max flow applications and reductions to LP |
|
| 12 (Nov 24) |
Approximation algorithms, cont'd Mon: Approximate k-centre Wed: PTAS for 0/1 knapsack; maximum cut (local search); approximate metric traveling salesman problem |
KT 11.2, DPV 9.2.2, slides KT 11.8, DPV 9.2.4; KT 12.4, slides |
No tutorial
this week |
|
| 12+ (Dec 1) |
Mon: Additional or overflow material
|
No tutorial this week |
Mon: A8 due (attention: unusual due day!) |
|
Academic integrity: Academic integrity is essential to the University of Toronto and so the University treats cases of cheating and plagiarism very seriously. Academic offences relevant to this course include using someone else's ideas or words without appropriate attribution; obtaining or providing unauthorized assistance on any assignment, test, or exam; misrepresenting your identity; and falsifying or altering documentation.
Accessiblity: If you have a disability or health condition that may require accommodation, please consult with AccessAbility Services (AA142, 416-287-7560, ability.utsc@utoronto.ca) as soon as possible. Enquiries to AccessAbility Services are confidential. Its staff will help assess needs and, if appropriate, will provide referrals and arrange accommodations.
Evaluation: There will be roughly eight homework assignments (not necessarily of equal weight) worth in total 40% of the course mark, a midterm test worth 20% of the course mark, and a final exam worth 40% of the course mark. A mark of at least 40% on the final exam is required to pass the course.
Homework grading: For each homework assignment we may grade only a selected (but not pre-announced) proper subset of the questions or parts thereof. In that event, the homework assignment will be graded out of the total weight of the graded part of the assignment.
Late homework policy: No late homeworks will be accepted. If you miss a homework deadline because of a medical or personal exigency, you must fill out, in plain text, and email the course instructor the Special Consideration Form as soon as possible. If the reason for missing the deadline is acceptable, the weight of the missed homework will be shifted to other components of your grade.
Homework collaboration policy: In each homework assignment you may collaborate with at most one other student who is currently taking CSCC73. If you collaborate with another student on an assignment, you and your partner must submit only one copy of your solution, with both of your names. The solution will be graded in the usual way and both partners will receive the same grade. Collaboration involving more than two students is not allowed. For help with your homework you may consult only the instructor, TAs, your homework assignment partner (if you have one), your textbook, and your class notes. You may not consult any other source.
Regrading policy:
To
submit a regrading request for an assignment or the midterm test you must
fill out, in plain text, this form
and email it to the course instructor no later than one week from the date
the graded assignment or test was made available to the class. (This
period may be shorter for the last assignment, to ensure timely delivery
of course grades.) Regrading requests made after the deadline will
not be accepted. As a result of a regrading request your grade in
the assignment may increase, remain unchanged, or decrease.
Regrading requests consume a large amount of the instructor's and TAs'
time, both of which are in short supply. Before making a
regrading request, you must read and understand the provided solutions and
think carefully about your own solution. To discourage frivolous
regrading requests we will apply the following rule: A regrading
request that does not result in increasing the grade of the
submitted assignment causes a "demerit'' to each of the student(s) who
submitted the assignment in question.
We will not consider regrading requests for an assignment submitted by a
student who has accumulated two such demerits.
Missed midterm test policy: If you miss the midterm test due to a medical or personal exigency, get in touch with your instructor immediately, and fill out the Special Consideration Form. There will be no make-up test, but if the reason for missing the test is acceptable, the weight of the missed midterm test will be shifted to the final examination.