CSC 373, Fall 2009
Algorithm Design and Analysis

General Information

Instructor Prof. Allan Jepson.
Email jepson at cs dot utoronto dot ca
Office Hour Tues. 5-6pm, D.L. Pratt 283D
Or by appointment.
Lectures FALL 2009 Tues. 6-8pm, Bahen, room 1210. Lectures start Sept. 14.
Tutorials FALL 2009 Tues. 8-9pm, Bahen, room 1210. Tutorials start Sept. 15.
Course Information Sheet Handout
Course Bulletin Board https://csc.cdf.toronto.edu/bb/YaBB.pl?board=CSC373H1F
Email-Newsgroup Policy There may be no response from 24 hours before an assignment is due, up to the actual time it is due.
Final Exam The Faculty of Arts and Science will schedule the exam sometime in October. Look up the time and place on the Examinations page.

Marking and Late Policy

See the Course Information Sheet.

Current Marks

Your marks are posted on the CDF secure website

A histogram of the current marks is given below. Your cummulative mark is obtained by summing your marks so far using the grading scheme weights and then scaling to the range 0-100%. For example, given just A1, TT1, and A2, marked out of 10, 20, and 20, respectively, your current cummulative mark is given by:
C = [(A1/10 * 5%) + (TT1/20 * 10%) + (A2/20 * 5%)]/(5 + 10 + 5)


Assignments

Links to assignments and related information are provided here.
Assignment
Description		 Percent Posting Date Due Date Links
Asgn #1 5% Sept.21 6:10pm, Oct. 6
at lecture. 		Solutions
Term Test #1 10% 6:10pm Sept.28   Solutions
Asgn #2 5% Oct. 14 6:10pm, Oct. 27
before lecture. 		Solutions
(same password as lecture notes)
Term Test #2 10% 6:10pm Nov. 3   Solutions
Asgn #3 5% Nov. 4 6:10pm, Nov. 17
before lecture. 		Solutions (revised 9:00am Sat. Nov. 21)
Term Test #3 10% 6:10pm Nov. 24    

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. 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 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 emailed to your cdf account, please do not distribute it outside of this class.
Date Notes Readings
Sept. 15 Intro to Greedy Design Skim Chpts 1-3
Read Chapter 4, up to end of Sec. 4.2
Sept. 22 Greedy Graph Algorithms
Dijkstra Demo 		Read Chapter 4 up to end of Sec. 4.8
Sept. 29 Divide and Conquer
Demo: Inversion Counting 		Read Chapter 5, up to end of Sec. 5.5
Oct. 6 Fast Fourier Transform
Spoken word: "Algorithms" 		Read Sec. 5.6
Oct. 13 Term Test #1 at 6:10pm, Lecture 7-9pm
Intro to Dynamic Programming (updated 6:30pm Tues., Oct. 13) 		Read Chapter 6, up to end of Sec. 6.7.
Oct. 20 Dynamic Programming in Graphs (modified: 2:28pm, Oct.20) Finish reading Chapter 6.
Oct. 27 Network Flow (updated Oct. 27, 11:24am)
Demo: Ford-Fulkerson Method 		Read Chapter 7, up to end of Sec. 7.3
Nov. 3 Term Test #2 at 6:10pm, Lecture 7-9pm
Applications of Network Flow
Project Selection 		Read sections 7.5 through 7.11.
Nov. 10 Linear Programming (revised 8:30am, Nov. 11). Read Sections 1 and 2 of Linear Programming and Sec. 11.6 of text.
Nov. 17 Duality in LPs (revised 3:20pm, Tues. Nov. 17)
Approximation Algorithms (revised 3:20pm, Tues. Nov. 17)
Demo: Makespan Approximation Alg.
 Read Chapter 11, except section 11.7.
Read section 2 of linear programming notes above.
Nov. 24 Term Test #3 at 6:10pm, Lecture 7-9pm
TBA: Local Search 		Read Chapter 12, up to the end of Sec. 12.5
Dec. 1
(Last Lecture) 		TBA: Randomized Algorithms Read Chapter 13, up to the end of Sec. 13.6.