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`
Office Hours	After class, Tues. and Thurs. until 5pm, beginning in lecture room, then in D.L. Pratt 283D
	Or by appointment.
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

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	TBA
Feb. 14, 16	TBA	Finish reading Chapter 6.
Tutorial Feb. 17	TBA
Reading Week Feb. 20-24	No classes or tutorials