CSC 373, Spring 2018
Algorithm Design, Analysis and Complexity

General Information

Instructor Prof. Allan Jepson.
Email jepson at cs dot utoronto dot ca
Office Hours Wed. 4:20-5pm in D.L. Pratt 283D (Note start at approx 4:20, since I am coming from class in Lash Miller)
Or by appointment.
Lectures L0101 and L2003: Mon., Wed. and Fri., 11am-noon, Bahen Center, BA 1190
 L0201: Mon., Wed. and Fri., 3-4pm, Lash Miller, LM 161
Tutorials Mon. 4-5pm, start Jan 15
As of Mon. Feb 12, all tutorials in BA1190.
Course Information Sheet Handout
Course Bulletin Board piazza.com/utoronto.ca/winter2018/csc373/home
Email, B. Board Policy Responses to email and bulletin board queries may take 1 to 2 business days.
Course MarkUs Page https://markus.teach.cs.toronto.edu/csc373-2018-01
Final Exam The Faculty of Arts and Science will schedule the exam later in the spring. Look up the time and place on the Examinations page.
Exam Aid Allowed: One 8.5 x 11 inch sheet of paper, printed both sides. For more info see Piazza, search "aid"

Marking Policy

See the Course Information Sheet.

Petitions

Contact your College Registrar if you are unable to complete an assignment or attend either a midterm test or the final exam due to illness or injury. You will need to have a medical professional complete a Verification of Student Illness or Injury Form.

Current Marks

Your unofficial marks will be updated during the term on the CS Teaching website.

Plagarism

We take plagarism very seriously. Everything you hand in to be marked, namely assignments, tests and the final exam, must represent your own work. Read How not to plagarize.

Assignments

Links to assignments, midterms, and related information are (will be) provided here.
Assignment
Description		 Percent Posting Date Due Date Links
A1 12% Jan 15 9:00am, Thurs, Jan 25 Sample Solutions (updated Jan. 31)
Midterm #1 12%   Jan. 31 Solutions
Questions: 11am, 3pm.
A2 (updated 4:25pm Feb. 6) 12% Feb 5 11:59pm, Fri, Feb 16 Sample Solutions
Midterm #2 12%   Mar. 12 Sample solutions for exams at:
11am, and 3pm.
Questions: 11am, 3pm.
A3 (Updated 5:05pm, Mar. 21) 12% Mar. 19 9:00am, Thurs, Mar. 29 Sample Solutions

Past Exams

Links to some previous CSC373 exams are provided by the Univ. of Toronto Libraries at old exams repository (search for CSC373H).

See the Previous Exam Study Guide for a table of exam questions that have been listed in terms of the major topic being tested, and roughly ranked by difficulty.

Lecture and Tutorial Materials

Links to some of the lecture notes and tutorial exercises are provided below.

My lecture slides are modified versions of those by Kevin Wayne.

Password for Lecture Notes. In order to respect the copyright, my lecture notes require a password to open them. The password will be announced in the first lecture. Please do not distribute it outside of this class. If you miss the first lecture, email me to ask for the password and include your UofT login name and student number.

Date Notes Optional Readings
Jan 5-12 Greedy Design 1 slide per page (1pp), 4 slides per page (4pp)

Greedy Graph Algorithms 1pp, 4pp (updated Jan 15, 2018)
Dijkstra demo 1pp, 4pp. 		Read Chapter 4, up to end of Sec. 4.7 of Kleinberg and Tardos.
Tutorial 1:
Mon, Jan 15 		Greedy algorithm exercises Solutions
Jan 17-22 Divide and Conquer (1pp), (4pp) (updated Jan 19, 2018)
Demo: Inversion Counting 1pp. 4pp. 		Read Chapter 5, up to end of Sec. 5.5 of Kleinberg and Tardos.
Tutorial 2:
Mon, Jan 22 		MST exercises Solutions
Jan. 22-29 Intro to Dynamic Programming (1pp), (4pp) (updated Jan 23, 2018)
 Read Chapter 6, up to end of Sec. 6.7.
Tutorial 3:
Mon, Jan 29 		Divide and Conquer exercises
 Solutions
Jan. 29 - Feb 5 Dynamic Programming in Graphs (1pp), (4pp) (updated Feb 2)
 Finish reading Chapter 6.
Tutorial 4:
Mon, Feb 5 		Dynamic Programming exercises (updated Feb 1, 2018) Solutions
Feb 5-9 Intro to Network Flow (1pp), (4pp) (updated Feb 8).
Proof of Flow Value Lemma.
Demo: Ford-Fulkerson Method (1pp), (4pp). 		Read Chapter 7, up to end of Sec. 7.3
Tutorial 5:
Mon, Feb 12 		Network Flow Intro exercises Sample Solutions
Feb 12-16 Network Flow Applications (Part I) (1pp), (4pp).
Network Flow Applications (Part II) (1pp), (4pp). 		Read Chapter 7.5, up to end of Sec. 7.11
Tutorial 6:
Mon, Feb 26 		Network Flow exercises Solutions
Feb 26-28 The set P and Polynomial Reductions (1pp), (4pp) Read Chapter 8, up to end of Sec. 8.2
Tutorial 7:
Mon, Mar 5 		Polynomial Reduction exercises Solutions
Mar 2 - NP and NP-Complete (1pp), (4pp). (Updated Mar.5)
co-NP (1pp), (4pp). (Updated Mar.5)
 Read Chapter 8.
Tutorial 8:
In office,
Mon, Mar. 12 		Self-reduction: Vertex-Cover Solutions
Tutorial 9:
Mon, Mar 19 		NP-complete exercises Solutions
Mar. 16 - Intro to Linear Programming (1pp), (4pp).
Duality in Linear Programming (1pp), (4pp). 		Read Sections 1 and 2 of Linear Programming and Sec. 11.6 of text.
Mar. 19 Lectures cancelled Mon., March 19. The tutorial will be held as normal.  
Tutorial 10:
Mon, Mar 26 		NP-complete and cliques (updated 11am, Mar. 29) Solutions (updated 11am, Mar. 29)
Mar. 26 - Apr. 4 Intro to Approximation Algorithms (1pp), (4pp).
Demo: Makespan Approx. Alg. (1pp), (4pp)
PTAS and FPTAS: Knapsack (1pp), (4pp) (updated 7pm, Apr. 4) 		Read Chapter 11, except section 11.7.
Tutorial 11:
Mon, Apr 2 		Approximation Algs Solutions
Tutorial 12:
Optional 		Weighted Vertex Cover Approx Solutions