Tutorial time and location: Fri 11-12, rm BV 260.
Prerequisites: CSCB63.
Text: Kleinberg and Tardos. Algorithm Design. Addison Wesley 2006.
Supplementary text: Dasgupta, Papadimitriou, and Vazirani. Algorithms. McGraw-Hill 2006. A close-to-final draft of this textbook is publicly available here.
Tentative weekly schedule:
| Week |
Lecture
(Tue) |
Tutorial
(Fri) |
Assignments
(Tue) |
| 1 (Sep 14-18) |
Greedy algorithms - Interval scheduling (KT* 4.1) - Minimum lateness scheduling (KT 4.2) * KT = Kleinberg & Tardos |
Review of Breadth-First Search
(KT 3.2, 3.3) |
Assignment 1 posted |
| 2 (Sep 21-25) |
Greedy algorithms (cont'd) - Shortest paths (KT 4.4) - Minimum Spanning Trees (KT 4.5) - Huffman codes (KT 4.8) |
Cache replacement (KT 4.3) Fractional knapsack |
|
| 3 (Sep 28-Oct 2) |
Divide & Conquer (D&C)
algorithms - D&C recurrences (KT 5.1-5.2) - Karatsuba's multiplication (KT 5.5) |
Review of complex numbers
(preparation for Fast Fourier Transform, next week) |
Assignment 1 due Assignment 2 posted |
| 4 (Oct 5-9) |
D&C algorithms (cont'd) - Fast Fourier Transform (DPV† 2.6, KT 5.6) † DPV = Dasgupta, Papadimitriou, & Vazirani |
No tutorial (Friday preceding
Thanksgiving) |
|
| 5 (Oct 12-16) |
D&C algorithms (cont'd) - Order statistics (KT 13.5) - Closest pair of points (KT 5.4) |
Q&A session |
|
| 6 (Oct 19-23) |
Dynamic Programming (DP)
algorithms - Longest increasing subsequence (DPV 6.2) - Optimal sequence alignment (KT 6.6) |
Longest common subsequence |
Assignment 2 due Assignment 3 posted |
| 7 (Oct 26-30) |
DP algorithms (cont'd) - Weighted interval scheduling (KT 6.1) - Susbset sum & knapsack (KT 6.4) |
DP and recursion, memoisation (KT 6.2) | |
| 8 (Nov 2-6) |
DP algorithms (cont'd) - Optimal binary search trees - DP-based shortest paths (KT 6.8, DPV 6.6) |
Matrix chain multiplication (DPV
6.5) |
|
| 9 (Nov 9-13) |
Maximum flow & applications - Ford-Fulkerson algorithm (KT 7.1) - Minimum cuts — max-flow min-cut (KT 7.2) |
Edmonds-Karp augmenting path
heuristic |
Assignment 3 due Assignment 4 posted |
| 10 (Nov 16-20) |
Max flow & applications (cont'd) - Bipartite graph matching (KT 7.5) - Disjoint paths (KT 7.6) |
Hall's theorem (KT 7.5, pp.
371-373) |
|
| 11 (Nov 23-27) |
Linear Programming (LP) - Examples, graphical representation (DPV 7.1) - Overview of simplex algorithm (DPV 7.6) - Duality (DPV 7.4) - Formulating optimisation problems as LPs |
Project selection (KT 7.11) |
|
| 12 (Dec 1-4) |
Approximation algorithms - LP relaxation: vertex cover (KT 11.6) - Greedy: set cover (KT 11.3) - DP: Knapsack (KT 11.8) |
No tutorial |
Assignment 4 due |
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 unauthorised 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 (SW-302, 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 four equally-weighted homeworks, a midterm exam and a final exam. The relative weights of these components towards the final mark are shown in the table below:
| Homework | 40% |
| Midterm | 20% |
| Final* | 40% |
*Important note: A mark of at least 35% on the final exam is required to pass the course. Repeated differently: If you receive less than 35% on the final exam you automatically fail the course, regardless of how well you have done on homeworks or the midterm exam.
Homework marking: For each homework assignment, we may mark only a selected subset of the questions (but solutions to all problems will be made available). In that event, the homework will be marked out of the total weight of the selected questions.
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 the Special Consideration Form. (In case of a medical exigency, you must also submit the UTSC Student Medical Certificate, completed and signed by your physician.) If we judge your reason for missing the deadline to be valid, we will use the average mark you achieved in other homeworks as your mark for the missed homework.
Homework collaboration policy: In each homework you may collaborate with at most one other student who is currently taking CSC C73. If you collaborate with another student on a homework, you and your partner must submit only one copy of your solution, with both of your names on the cover. The solution will be graded in the usual way and both partners will receive the same mark. Collaboration involving more than two students is not allowed. For help with your homework you may consult only the instructor, TAs, your homework partner (if you have one), your textbook and your class notes. You may not consult any other source.
Remarking policy: If your request concerns a simple addition error, see the instructor. To make any other kind of remarking request, you must fill this form, attach it to your homework assignment or test, and give it to the instructor of the course no later than one week from the date the marked assignment or test was made available to the class. Remarking requests made after this deadline will not be accepted.
Missed midterm test policy: If you miss the midterm test due to a medical or other serious exigency, get in touch with your instructor immediately, and fill out the Special Consideration Form. (In case of a medical exigency, you must also submit the UTSC Student Medical Certificate, completed and signed by your physician.) There will be no make-up test, but if we consider your reason for missing the test to be valid, we will use your final examination mark to compute your mark for the missed midterm test.
Attendance in tutorials: There will be material presented only in tutorial and not discussed in the lectures, which I will expect you to know and on which you may be tested in homeworks or exams.
Nov 22 — Assignment #4: ...has been posted in the Course Documents section of this web page. You are equipped to do all questions except 3(b). After the next lecture (Tue Nov 24), you will be equipped to do that one as well.
Nov 19 — Course evaluations: Student evaluations for this course will be done on-line. (This will save some trees, and will also save you the trouble of learning how to spell my name.) At some point between today and Dec 3, please log into the intranet and fill out the CSCC73 course evaluation.
I see the results of your evaluations anonymously, and only after I have submitted final marks for the course. Thus, there is no risk that your comments will adversely or favourably influence my grading, individually or collectively. Student comments can help us improve our teaching. So, I would appreciate your taking the time to let me know what you think worked well and, especially, what didn't.
Nov 11 — Change to office hours on Mon Nov 16: Due to a conflict with another commitment, my office hours next Monday (November 16) will be 2:30-3:30 (instead of the usual 3-4). This change is in effect only for next week.
Nov 5 — Correction to Assignment #2 solutions: As Robert pointed out to me, the assumption that n is a power of 2 in the algorithm for Question 4, Part (b) isn't really without loss of generality. The case when n is odd has to be treated specially: we test if A[n] happens to be the majority, and if so we return it; if it isn't, we deal with A[1..n-1], which now has an even number of elements, as described before. A revised version of the solutions that handles arbitrary n (not only powers of 2) was posted at about 6:30pm today.
Nov 2 — Assignment #2 solutions: ...have been posted in the Course Documents section of this web page.
Oct 27 — Assignment #3: ...has been posted in the Course Documents section of this web page. After today's lecture (Tue Oct 6), you will be equipped to do all questions.
Oct 18 — The perils of careless cut-and-paste: Line 8 of the pseudocode for Karatsuba's algorithm in Q1 or Assignment 2 had a typo: it was (re)defining xL, when it should have been defining yR. (A corrected version of the assignment was posted at about 9:40pm today.) In addition, the pseudocode for the same algorithm cited in the October 16 announcement below also contained some typos: xR and yR should have been assigned the rightmost ⌊n/2⌋ bits of x and y respectively (and not the leftmost ⌊n/2⌋ bits as the announcement incorrectly used to state); and in the case of yR the bits are taken from y (and not from x, as the announcement, again incorrectly, used to state). The October 16 announcement was also corrected. Thanks to William Jia for pointing out these typos, and my apologies for the confusion.
Oct 16 — Clarification on Question 1 and extension of due date for Assignment 2: After fielding several questions about Question 1, it has become clear that the question is ambiguous — in part because I never fully spelled out Karatsuba's algorithm. I have now reformulated that question, and posted a revised version of the assignment. The revision affects only Question 1. I am also extending the due date of the homework to Fri Oct 22 at 10:30am.
Please read the following before you look at the revision of the question. Following is the pseudocode of Karatsuba's algorithm as given in DPV.
multiply(x, y) n := max(size(x), size(y)) if n=1 then return x*y xL := leftmost ⌈n/2⌉ bits of x xR := rightmost ⌊n/2⌋ bits of x yL := leftmost ⌈n/2⌉ bits of y yR := rightmost ⌊n/2⌋ bits of y P1 := multiply(xL, yL) P2 := multiply(xR, yR) P3 := multiply(xL+xR, yL+yR) return P1*2n + (P3-P1-P2)*2n/2 + P2There are two problems here:
(1) If x and y don't have the same size and, say, y is shorter than x, the definition of yL and yR isn't quite right: The two parts of y will not form a proper partition of y. (In fact, if y is much shorter than x, there might not even be ⌈n/2⌉ bits in y!) What is presumably intended here is that, if one of the two numbers is shorter than the other, then we should pad out the shorter one to exactly n bits by adding enough 0's to the left.
(2) The formula for the value returned (that combines the results of the recursive calls) is not correct when n is an odd number, since in that case n/2 is not an integer. The correct formula is P1*22*⌊n/2⌋ + (P3-P1-P2)*2⌊n/2⌋ + P2. Note that this problem can't be circumvented simply by assuming that n is a power of 2: although the recursive computations of P1 and P2 involve numbers whose size is n/2, and therefore also a power of 2, the recursive computation of P3 might not, since xL+xR or yL+yR could have (n/2)+1 bits each, and this is not a power of 2. As I mentioned in class, and left as an exercise, it is possible to avoid this problem by replacing the computation of P3 by another multiplication that involves two n/2-bit numbers, and requires some additional shifts and additions to compute the value to be returned.
Oct 13 — Additional office hours and this week's tutorial: Because of the exam I will hold extra office hours on Thursday October 15, 4-5pm in my office (SW-627). This week's tutorial will be another opportunity to ask questions before the exam. Robert will not cover new material, but will be available to answer questions you may have about the material.
Oct 11 — Midterm exam:
Time and place: Friday October 16, 3-5 pm, in room HW-214.
Material covered: Greedy algorithms and divide-and-conquer algorithms, up to and including material to be presented in lecture on Tuesday October 13.
Aids allowed: The exam will be closed book. You may bring an 8.5x11 hand-written, non-photocopied ``cheat sheet''; you may use both sides, if you wish. During the exam you may not carry on your person or keep on your desk any electronic computation, communication, or storage devices (such as calculators, mobile phones, laptops, and ipods).
Oct 9 — Solutions to Assignment #1: ...have been posted in the Course Documents section of this web page.
Oct 8 — Samuel Beatty in-course scholarships: Several of you are eligible for these scholarships. You can find more about them, including information on how to apply, here. Application deadline: November 13.
Oct 5 — Assignment #2: ...has been posted in the Course Documents section of this web page. You are already equipped to do Questions 1, 2, and 4. After tomorrow's lecture (Tue Oct 6), you will be equipped to do Question 3 too.
Sep 27 — CMS Student Seminar on Graduate Studies:
Sep 25 — Correction and extention for Assignment #1: The end of Question 5(a) should be ``and Huffman's algorithm may produce a codeword of length 1''. (instead of ``must produce...'') The due date for this assignment is now extended to Friday October 2 at 10:30am (before your tutorial). A revised version of Assignment 1 was posted at about 7:30pm today. The only change is the one described above (and the due date). Please obtain a new copy of the assignment and discard any previously downloaded versions. My apologies for this error.
Sep 21 — Date of midterm exam: The midterm exam will be on Friday October 16, 3-5 pm, in room HW-214.
Sep 20 — Correction to Assignment #1: There was a mistake in the statement of Question 2(a): the set Bi should be a subset of the jobs not yet considered, i.e., the set of jobs in variable U after i iterations of the while loop (and not a subset of the set of jobs {i+1, i+2, ..., n}, as the question stated). A revised version of Assignment 1 was posted at about 5:40pm today. The only change is the one described above. Please obtain a new copy of the assignment and discard any previously downloaded versions. My apologies for the error, and thanks to Robert Danek who pointed it out.
Sep 20 — Change to office hours for Mon Sep 21: Because of a Faculty and Staff meeting of the Department of Computer and Mathematical Sciences, my office hours on Mon Sep 21 will be 5-6pm (instead of the usual time, 3-4pm).
Sep 17 — Assignment #1: ...has been posted in the Course Documents section of this web page. You are already equipped to do Questions 1 and 2. After the lecture next Tuesday, you will be equipped to do the remaining three.
Sep 10 — H1N1 Planning: Please consult regularly the university's preparedness site for information on how to protect yourself and your community from the H1N1 virus.
Sep 9: Welcome to CSCC73.
Our first topic will be greedy algorithms. This is treated in Chapter 4 of the textbook. In the first lecture (Tue Sep 15), I plan to present greedy algorithms for interval scheduling (Section 4.1) and minimum lateness scheduling (Section 4.2). I suggest that you get in the habit of (at least) skimming the course material in the text before I present it in class, and reviewing it carefully very soon after.
The first tutorial will be on Fri Sep 18. Robert will review breadth-first search of graphs (a topic you encountered in CSCB63), in preparation for material I plan to present in the second week (Dijkstra's algorithm for shortest paths in weighted directed graphs).
In our treatment of algorithms, we will be interested in both their correctness and their time (and sometimes space) complexity. We will make extensive use of asymptotic notation (big-oh etc). You should be well-acquainted with this topic from CSCB63. You can find a terse review of this material here, and a more leisurely account in Chapter 2 of the textbook.