CSCC73 -- Algorithm design and analysis

Fall 2024


Index of this document


Contact information and meeting times

Instructor:  Vassos Hadzilacos
Office hours:  Mon 4-5 and Wed 3:30-4:30, or by appointment
Office:  IA 4024 (Scarborough campus);  SF 2304B (St. George campus)
Telephone:  416-287-7256 (Scarborough campus);  416-978-6028 (St. George campus)
Email:  vassos@cs.toronto.edu
TAs:  Lingfei Cai, Yulong Liu, Christopher Nathanael, Ali Orozgani

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/

Course forum page:   https://piazza.com/utoronto.ca/fall2024/cscc73/home
Lecture times and locations:  LEC01 Mon 11-12 (IA 1150) and Wed 9-11am (IA 2021); LEC02 Mon 1-2 (IA 1150) and Wed 1-3 (IA 1150). Tutorial times and locations:  TUT01 Fri 10-11 (HW 214), TUT02 Fri 1-2 (HW 215), TUT03 Thu 4-5 (IC 130).

Back to the index


Course content

Course goals:   To introduce the main algorithmic paradigms (greedy, divide-and-conquer, dynamic programming, linear programming) through concrete examples. Emphasis on algorithmic thinking and problem-solving, not on programming.

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): 

Speak, then, and tell everything.  For, it comforts those in pain
To know before hand all the agony they still must bear.
--Aeschylus, Prometheus Bound

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!)

* KT = Kleinberg & Tardos
† DPV = Dasgupta, Papadimitriou, & Vazirani

Back to the index


Course policies

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.

Back to the index


Course documents

In this space we will make available course documents in PDF.

Back to the index


Course forum

We will use Piazza as the platform for class announcements and discussions. 

The URL of the CSCC73 Piazza page is: https://piazza.com/utoronto.ca/fall2024/cscc73/home.

Guidelines for posting on Piazza:


Document maintained by Vassos Hadzilacos