CSC 373, Spring 2016
Algorithm Design, Analysis and Complexity


General Information

Instructor Prof. Allan Jepson.
Email jepson at cs dot utoronto dot ca
Office Hours Wed. 4:10-5pm (I'm coming from my class in BA1200) in D.L. Pratt 283D
Or by appointment.
Lectures L0101: Mon., Wed. and Fri., 11am-noon, Wilson Hall, WI 1017
 L0201: Mon., Wed. and Fri., 3-4pm, Bahen Center, BA 1200
Tutorials Mon., 4-5pm, start Jan 18. Tutorial room assignment is according to first letter in your family name:
A through D: Room SS1069
E through I: Room WI1017
J through L: Room SS1083
M through Q: Room SS1084
R through V: Room SS1085
W through Z: Room SS1070
Course Information Sheet Handout
Course Bulletin Board https://csc.cdf.toronto.edu/mybb/forumdisplay.php?fid=459
Email, B. Board Policy Responses to email and bulletin board queries may take 1 to 2 business days.
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.

Marking Policy

See the Course Information Sheet.


Petitions

Contact your College Registrar if you are unable to 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 CDF secure 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.

CDF Information

By registering in this course you should have a CDF account. In this course you will need this CDF account only to post messages to the bulletin board. For information on CDF see http://www.cdf.toronto.edu/. Before going to a CDF lab, or to the course bulletin board, you need to look-up your CDF account.

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 CDF login name and UofT student number.

Date Notes Optional Readings
Jan 11-15 Design of Greedy Algorithms

Greedy Graph Algorithms
Read Chapter 4, up to end of Sec. 4.7 of Kleinberg and Tardos. Check out Dijkstra Demo.
Mon, Jan 18 Example Proof: Prim is Promising  
Tutorial:
Mon, Jan 18
Greedy algorithm exercises Solutions
Wed, Jan 20 to
Mon, Jan 25
Intro to Dynamic Programming

New slide 12.5 of Intro to Dynamic Programming

Matrix Chain Multiplication (by Zbigniew Ras)
Starting with this lecture, for pdf's with only one page per slide try changing URL for lecture notes from *_4pp.pdf to *_1pp.pdf. No promises.

Read Chapter 6, up to end of Sec. 6.7.
Tutorial:
Mon, Jan 25
On learning from lectures.

MST and Dyn. Prog. exercises.
Solutions.
Mon, Jan 25 to
Mon, Feb 1
Dynamic Programming in Graphs Finish reading Chapter 6.
Tutorial:
Mon, Feb 1
Dyn. Prog. exercises, Part II Solutions.
Mon, Feb 1 to
Fri, Feb 5
Network Flow

Proof of Flow Value Lemma Revisited
Read Chapter 7, up to end of Sec. 7.3
Demo: Ford-Fulkerson Method
Midterm Exam #1

No tutorials on Mon. Feb 8

See right for exam time and room.
Midterm Exam #1, Mon, Feb 8 at 6:10-7pm

Examination rooms are assigned by first two letters of your family name. See table entry to the right.
We reserve the right to deduct marks for writing the exam in the incorrect room (since this will cause a delay in seating people).
The rooms are all in the Haultain Building.
Family Name Room
A through Gh (inclusive)HA 316
Gi through Se (inclusive)HA 403
Sf through Ta (inclusive)HA 409
Tb through Z (inclusive)HA 410

Solutions.
Mon, Feb 8 to
Fri, Feb 12
Applications of Network Flow
Read sections 7.5 through 7.11.
Tutorial:
Mon, Feb 22
Review Midterm Solutions Solutions.
Tutorial:
Mon, Feb 29
Network Flow exercises Solutions.
Mon, Feb 22 to
Wed, Mar 2
P and Polynomial Reductions

NP and NP-Completeness
Read Chapter 8, up to end of Sec. 8.4
Fri, Mar 4 co-NP Finish reading Chapter 8.
Tutorial:
Mon, Mar 7
P and NP exercises Solutions.
Mar. 7, 14 Linear Programming

Intro to Duality in LPs
Read Sections 1 and 2 of Linear Programming and Sec. 11.6 of text.
Midterm Exam #2

No tutorials on Mon. March 14

See right for exam time and room.
Midterm Exam #2, Mon, March 14 at 6:10-7pm

Examination rooms are assigned by first letters of your family name. See table entry to the right. The rooms are both in the Exam Center.
We reserve the right to deduct marks for writing the exam in the incorrect room (since this will cause a delay in seating people).
Family Name Room
A through L (inclusive)EX 310
M through Z (inclusive)EX 320

Solutions.
Mar. 16-23 Approximation Algorithms (Updated 1:00pm, March 22, 2016.) Read Chapter 11, except section 11.7.
Demo: Makespan Approximation Alg.
Tutorial:
Mon, Mar 21
Review Midterm #2 Solutions Solutions.
Tutorial:
Mon, Mar 28
LP and Approximation Exercises Solutions.
Mon, Mar 28 to
Fri, Apr 1
Randomized Algorithms Read Chapter 13, up to the end of Sec. 13.6.
Tutorial:
Mon, Apr 4
Approximation Exercises Solutions
Apr 4-8 Local Search Read Chapter 12, up to the end of Sec. 12.5
Final Exam Check the course bulletin board for announcemnts, including what aids you can bring to the exam. Exam Content: Lecture notes and tutorial exercises listed above.

Resources: UofT Stress Management
See also Strategies for Reducing Stress