Tutorial times and locations: Fri 11-12, rm BV 260.
Prerequisites: CSCB63.
Texts:
Kleinberg and Tardos. Algorithm Design. Addison Wesley 2006.
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 13-17) |
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 20-24) |
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 27-31) |
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 4-8) |
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 11-15) |
D&C algorithms (cont'd) - Order statistics (KT 13.5) - Closest pair of points (KT 5.4) |
Q&A session No tutorial |
|
| 6 (Oct 18-22) |
Dynamic Programming (DP)
algorithms - Longest increasing subsequence (DPV 6.2) - Optimal sequence alignment (KT 6.6) |
Longest common subsequence Q&A session (day before midterm exam) |
Assignment 2 due Assignment 3 posted |
| 7 (Oct 25-29) |
DP algorithms (cont'd) - Weighted interval scheduling (KT 6.1) - Susbset sum & knapsack (KT 6.4) |
DP and recursion, memoisation
(KT 6.2) Longest common subsequence |
|
| 8 (Nov 1-5) |
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 8-12) |
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 15-19) |
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 22-26) |
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 (Nov 29-Dec 3) |
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.
Dec 9 — Assignment #4 has been marked: You may pick up your paper during exam office hours (see December 3 "Announcements related to the final exam" below). You can also view your Assignment 4 mark on the intranet.
Dec 3 — Current marks: You can now view your marks in Assignments 1-3 and the midterm exam on the intranet. While you are at it, and if you have not done so already, please fill out the on-line course evaluation. (If you have done so, thank you!)
Dec 3 — Announcements related to the final exam:
When and where: Wed Dec 16, 9am-12noon in room MW 160.
What: Everything covered in this course.
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 computation, communication, or storage electronic devices (such as calculators, mobile phones, laptops, and ipods).
Pre-exam office hours: Fri Dec 10 3-4pm, Mon Dec 13 3-4pm, Tue Dec 14 3-4pm. Also feel free to contact me by email.
Dec 2 — Return of Assignment #3: Several of you did not pick up Assignment 3 in tutorial last week. You may pick it up from my office on Friday December 3. I will be there more of the time, except during 11:30-1:30.
Dec 1 — Solutions to Assignment #4: ...have been posted in the Course Documents section of this web page.
Nov 22 — Course evaluations: Student evaluations for this course will be done on-line. At some point between today and Dec 6, 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 — Solutions to Assignment #3: ...have been posted in the Course Documents section of this web page. Please note that Question 2 was mis-stated so it will not be marked, and the assignment will be graded out of 40 points &mdash see the gray box on page 2 of the Solutions for details. My apologies for this error.
Nov 9 — Assignment #4: ...has been posted in the Course Documents section of this web page. After this week's lecture, you will be equipped to do Questions 1-2. After next week's lecture, you will be equipped to do Questions 3 and 4(a). After the lecture on November 23, you will be equipped to do Question 4(b).
Nov 8 — Change to office hours for today: Due to a conflict, my office hours today will be 2:30-3:30 (instead of the usual 3-4).
As always, you are welcome to make an appointment for another time, or
to drop by my office unannounced (at the risk of having to come back,
if I happen to be busy at that time).
Oct 18 — Midterm exam:
Time and place: Saturday October 23, 1-3 pm, in room HW-215.
Material covered: Greedy algorithms and divide-and-conquer algorithms, up to and including material presented in lecture on Tuesday October 12.
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 18 — Assignment #3: ...has been posted in the Course Documents section of this web page. After this week's lecture, you will be equipped to do Questions 1-3. After next week's lecture, you will be equipped to do Questions 4-5.
Oct 1 — Solutions to Assignment #1: ...have been posted in the Course Documents section of this web page.
Sep 28 — Assignment #2: ...has been posted in the Course Documents section of this web page. By the end of today's lecture, you will be equipped to do Questions 1-3. After next week's lecture, you will be equipped to do Questions 4-5. The extra credit Question 6 refers to material we will discuss two weeks from today.
Sep 17 — TA's office hours announced: Eric will be holding office hours on Friday 3-5 in room BV 359, only on weeks before a homework is due and before the midterm test.
Sep 17 — Office hours on Monday October 20 rescheduled: Due to a conflict I will not be able to have my office hours at the regular time on Monday October 20. Instead, I will hold office hours on Friday October 24, 3-4pm, in SW-627. My apologies for any inconvenience.
Sep 14 — Assignment #1: ...has been posted in the Course Documents section of this web page. By the end of today's lecture, you will be equipped to do Questions 1-3. After next week's lecture, you will be equipped to do the remaining two.
Sep 1: Welcome to CSCC73.
Our first topic will be greedy algorithms. This is treated in Chapter 4 of the Kleinberg-Tardos textbook (KT) and Chapter 5 of the Dasgupta-Papadimitriou-Vazirani textbook (DPV). In the first lecture (Tue Sep 14), I plan to present greedy algorithms for interval scheduling (KT §4.1) and minimum lateness scheduling (KT §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 16. Your TA 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.