CSCC73 -- Algorithm design and analysis

Fall 2017


Index of this document


Contact information and meeting times

Instructor:  Vassos Hadzilacos
Office hours:  Wed 11-12:30, or by appointment
Office:  IC 448 (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:  Bryan Chan, Yasaman Mahdaviyeh, Sadegh Rahnamoon, Brendan Zhang
Office hours:  Thu 4-6pm
Office: IC 400A
Course web page:  http://www.cs.toronto.edu/~vassos/teaching/c73/

Course forum page: 
https://www.piazza.com/mail.utoronto.ca/fall2017/cscc73

Lecture times and location:  Mon 11-12 and Wed 9-11 (IC 220)

Tutorial times and locations:  Tut 1 Fri 10 (BV 355), Tut 2 Tue 4 (IC 212), Tut 3 Fri 1 (BV 355), or Tut 4 Fri 9 (AA 205), as assigned

Back to the index


Course content

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

Prerequisites:   CSCB63, STAB52, and enrolment in a computer science subject POSt (or CGPA of 3.0 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 of
Lectures
Tutorials
Assignments
Sep 3
Greedy algorithms

Mon:  Labour Day (no class)
Wed:  Course goals and logistics.  Interval scheduling (KT* 4.1)


No tutorial this week



Sep 10
Greedy algorithms, cont'd

Mon:  Minimum lateness scheduling (KT 4.2)
Wed:  Dijkstra's single-source shortest paths algorithm (KT 4.4, DPV 4.3-4.4), fractional knapsack


Practice with greedy algorithms



Mon:  A1 posted

Sep 17
Wrap up greedy algorithms, start divide & conquer (D&C) algorithms

Mon: Huffman codes (KT 4.8, DPV† 5.2)
Wed: D&C recurrences (KT 5.1-5.2, DPV 2.2), Karatsuba's integer multiplication (KT 5.5, DPV 2.1)


Review of complex numbers --- preparation for the Fast Fourier Transform


Mon: A1 due, A2 posted

Sep 24
D&C algorithms, cont'd

Mon: Fast Fourier Transform (DPV 2.6, KT 5.6)
Wed: Fast Fourier Transform, cont'd (DPV 2.6, KT 5.6)


Strassen's matrix multiplication (DPV 2.5)


Mon: A2 due, A3 posted
Oct 1 D&C algorithms, cont'd

Mon: Closest pair of points (KT 5.4)
Wed: Order statistics (KT 13.5, DPV 2.4)


Practice with D&C algorithms ---
Counting inversions in a pair of lists (KT 5.3)


Mon: A3 due, A4 posted
Oct 8
Thanksgiving and Reading Week (no classes)
Oct 15
Dynamic Programming (DP) algorithms

Mon: Longest increasing subsequence (DPV 6.2)
Wed: Optimal sequence alignment (KT 6.6, DPV 6.3), weighted interval scheduling (KT 6.1)


Midterm 2016 review



Mon:
A4 due, A5 posted
Oct 22
DP algorithms, cont'd

Mon: Optimal binary search trees
Wed: Knapsack & susbset sum (KT 6.4, DPV 6.4), optimal fingering of music scores, DP and recursion, memoisation


TBA


Mon:
A5 due, A6 posted
Sat 1-3pm: Midterm test

Oct 29
DP algorithms, cont'd
 
Mon: Bellman-Ford single-source shortest paths algorithm (KT 6.8)
Wed: Floyd-Warshall all-pairs shortest paths algorithm; transitive closure; detecting and identifying negative weight cycles (DPV 6.6)


TBA


Nov 5
Maximum flow & applications

Mon: Max flow problem,  Ford-Fulkerson algorithm (KT 7.1, 7.2, DPV 7.2)
Wed: Analysis of Ford-Fulkerson algorithm, max-flow min-cut theorem (KT 7.2, 7.3, DPV 7.2)


TBA



Mon: A6 due, A7 posted
Nov 12
Max flow & applications, cont'd

Mon: Bipartite graph matching (KT 7.5, DPV 7.3)
Wed: Bipartite graph vertex cover; disjoint paths in directed and undirected graphs (KT 7.6)


TBA

Nov 19
Linear Programming (LP)

Mon: Motivation, examples, the geometry of LPs (DPV 7.1)
Wed: LP algorithms (DPV 7.6),  formulating optimization problems as LPs, reductions.


TBA


Mon: A7 due, A8 posted

Nov 26
LP, cont'd

Mon: Integer LPs, Zero-One LPs, formulating optimization problems as ILPs.  Matrix notation for  LPs, min/max standard forms.  Duality (DPV 7.4)
Wed: Duality (cont'd).  Difference constraints.  Johnson's all-pairs shortest path algorithm.




TBA



Dec 3
Mon:  Wrap-up (last day of classes)
No tutorial this week Mon: A8 due

* 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 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 roughly eight homework assignemtns worth in total 40% of the course mark (each assignment will be worth 4-6% of the course mark), a midterm exam 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.  (Repeated differently:  If you receive less than 40% on the final exam you automatically fail the course, regardless of how well you have done on the homework assignments or the midterm exam.)

Homework marking:  For each homework assignment, we may mark only a selected (but not preannounced) subset of the questions.  In that event, the homework assignment 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 U of T Verification of Student Illness or Injury Form, 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 homework assignments as your mark for the missed homework.

Homework  collaboration policy:   In each homework assignment you may collaborate with at most one other student who is currently taking CSC C73.   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 mark.  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, you must fill out this form in plain text, and email it to the course instructor no later than one week from the date the graded assignment was made available to the class. (This period may be shorter for the last assignment, to ensure timely delivery of course grades.) To submit a regrading request for the midterm test, you must fill out this form, attach your test to it, and hand it to the course instructor no later than one week from the date the graded test was made available to the class.  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 already accumulated two such demerits.

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 U of T Verification of Student Illness or Injury Form, completed and signed by your physician.)  There will be no make-up test, but if we judge 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, on which you may be tested in homework assignments or exams.

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.  This service is free to use, but requires registration.

To register, follow the link below and provide the access code announced in the first lecture.  For idenitification reasons, I would appreciate it if you would use your real name and your @mail.utoronto.ca or @utoronto.ca address as your email contact when you register in Piazza.  If you have privacy concerns about this, please see me to discuss alternatives.  The bottom line is that I must be able to identify any individual on the forum as a student registered in the course; individuals for whom this is not the case may be removed from the class forum without warning.

The URL of the CSCC73 Piazza page is:  https://www.piazza.com/mail.utoronto.ca/fall2017/cscc73.

Here are the course guidelines for posting on Piazza:
I will endeavour to monitor the discussions on Piazza a couple of times a week.

Although Piazza is useful for certain types of communication, the best way to have your questions about course material answered remains the old-fashioned one: visiting your instructor during office hours.


Document maintained by Vassos Hadzilacos