CSC 373, Spring 2012

CSC 373, Spring 2012
Algorithm Design, Analysis and Complexity

General Information

Instructor	Prof. Allan Jepson.
Email	`jepson at cs dot utoronto dot ca`
Exam Office Hours	See the course bulletin board.
Lectures	Tues. and Thurs., 2-3:30pm (note extra half hour), Sidney Smith Hall, Room 2106. Lectures start Jan. 10.
Tutorials,	Fri., 3-4pm, Sidney Smith Hall, Room 2106. Tutorials start Jan. 20.
Course Information Sheet	Handout
Course Bulletin Board	https://csc.cdf.toronto.edu/bb/YaBB.pl?board=CSC373H1S
Email, B. Board Policy	There may be no response from 24 hours before an assignment is due, up to the actual time it is due.
CS Course Help Center	Another place to get help with the course content is the DCS help center.
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 and Late Policy

See the Course Information Sheet.

Medical Issues

If are unable to hand in an assignment or write an due to a serious medical condition, have your doctor complete a UofT Student Medical Certificate available from UofT Health Services Forms. Submit the completed certificate to your instructor.

Current Marks

Your unofficial marks will be posted on the CDF secure website.

Assignments

Links to assignments and related information are (will be) provided here.

Assignment Description	Percent	Posting Date	Due Date	Links
A1	15%	Feb. 10	3:10pm, Wed, Feb 10	Sample solutions Marking Weights
A2 (updated 10:15 Feb. 22)	15%	Feb. 15	3:10pm, Fri, March 2.	Sample solutions Marking Weights
A3	15%	Mar. 10	3:10pm, Fri, March 23.	Sample solutions Marking Weights
A4	15%	Mar. 23	3:10pm, Fri, April 6.	Sample solutions Marking Weights (See course bulletin board for office hours before the exam.)

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.

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 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.

Date	Notes	Readings	Optional Readings
Jan. 10, 12	Polynomial Reductions, NP and NP-Completeness	Read Chapter 8, up to end of Sec. 8.4
No Tutorial Jan. 13		Read Chapter 8, up to end of Sec. 8.6.
Jan. 17, 19	Finish NP-Completeness Notes A worked example: clique.txt co-NP Updated (9:45pm Jan. 18).	Finish reading Chapter 8.
Tutorial Jan. 20	Worked Example: Scheduling Sales Meetings	Finish reading Chapter 8.
Jan. 24, 26	Design of Greedy Algorithms Greedy Graph Algorithms	Read Chapter 4, up to end of Sec. 4.7.	Dijkstra Demo
Tutorial Jan. 27	Worked Example: Graphical Steiner Trees	A. Santuari's Notes on Steiner Trees
Jan 31, Feb 2	Example Proof: Prim is Promising Divide and Conquer Karatsuba Alg. on polynomials	Read Chapter 5, up to end of Sec. 5.5.	Fast Fourier Transform, Audio: "Algorithms" Section 5.6 of text.
Tutorial Feb. 3	Worked Example: Mod of Powers Notes on Hidden Lines Hidden line figures
Feb. 7, 9	Intro to Dynamic Programming Matrix Chain Multiplication (by Zbigniew Ras): PPT slides or PDF handouts	Read Chapter 6, up to end of Sec. 6.7.
Tutorial Feb. 10	Dyn. Prog. Exam Question Sample Soln.
Feb. 14, 16	Dynamic Programming in Graphs	Finish reading Chapter 6.
Tutorial Feb. 17	Tutorial Notes. LongestIncSubsequence
Reading Week Feb. 20-24	No classes or tutorials
Feb. 28 Mar. 1	Network Flow	Read Chapter 7, up to end of Sec. 7.3	Demo: Ford-Fulkerson Method
Tutorial Mar. 2	Tutorial Notes. final2008F_q5.pdf residualGraph.pdf
Mar. 6, 8	Applications of Network Flow	Read sections 7.5 through 7.11.
Tutorial Mar. 9	TBA
Mar. 13, 15	Linear Programming Duality in LPs (short)	Read Sections 1 and 2 of Linear Programming and Sec. 11.6 of text.	Duality in LPs (longer)
Tutorial Mar. 16	Tutorial Notes. a4_10.pdf a4_10Soln.pdf
Mar. 20, 22	Approximation Algorithms Begin: Randomized Algorithms	Read Chapter 11, except section 11.7.	Demo: Makespan Approximation Alg.
Mar. 27, 29	Continue Randomized Algorithms.	Read Chapter 13, up to the end of Sec. 13.6.
Apr 3, 5	Local Search	Read Chapter 12, up to the end of Sec. 12.5
Fri Apr 6	University is closed. No lecture or tutorial.
Final Exam	Check the course bulletin board for announcemnts, including what aids you can bring to the exam.	Exam Content: Lecture notes and text book sections listed above.