|Instructor||Prof. Allan Jepson.|
|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||
|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.|
See the Course Information Sheet.
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.
Your unofficial marks will be updated during the term on the CS Teaching website.
|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|
|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.
|A3 (Updated 5:05pm, Mar. 21)||12%||Mar. 19||9:00am, Thurs, Mar. 29||Sample Solutions|
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.
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.
Mon, Jan 15
|Greedy algorithm exercises||Solutions|
Divide and Conquer
(4pp) (updated Jan 19, 2018)
Demo: Inversion Counting 1pp. 4pp.
Read Chapter 5, up to end of Sec. 5.5 of Kleinberg and Tardos.
Mon, Jan 22
Intro to Dynamic Programming
(4pp) (updated Jan 23, 2018)
||Read Chapter 6, up to end of Sec. 6.7.|
Mon, Jan 29
Divide and Conquer exercises
|Jan. 29 - Feb 5||
Dynamic Programming in Graphs
(4pp) (updated Feb 2)
||Finish reading Chapter 6.|
Mon, Feb 5
|Dynamic Programming exercises (updated Feb 1, 2018)||Solutions|
Intro to Network Flow
(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
Mon, Feb 12
|Network Flow Intro exercises||Sample Solutions|
Network Flow Applications (Part I)
Network Flow Applications (Part II) (1pp), (4pp).
Read Chapter 7.5, up to end of Sec. 7.11
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|
Mon, Mar 5
|Polynomial Reduction exercises||Solutions|
|Mar 2 -||
NP and NP-Complete
(4pp). (Updated Mar.5)
co-NP (1pp), (4pp). (Updated Mar.5)
|Read Chapter 8.|
Mon, Mar. 12
Mon, Mar 19
|Mar. 16 -||
Intro to Linear Programming
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.|
Mon, Mar 26
|NP-complete and cliques (updated 9:50am, Mar. 22)||Solutions|
|Mar. 26 - Apr. 4||
Intro to Approximation Algorithms
Demo: Makespan Approx. Alg. (1pp), (4pp)
PTAS and FPTAS: Knapsack (1pp), (4pp).
|Read Chapter 11, except section 11.7.|