CSC 363H1Y: Computational Complexity and Computability
Summer 2006

Course Information

Instructor: Richard Krueger

email:

Lectures: Tuesdays, 6pm-8pm in SF 1101

Tutorials: Tuesdays, 8pm-9pm (tutorials begin the first week!)

BA 1210   with Anthony To   (last names A to L)

BA 1220   with Periklis Papakonstantinou   (last names M to Z)

Tutors: Anthony To, Duy Minh Dang, Periklis Papakonstantinou, Tim Fowler

Office hours: by appointment, or

Wednesdays, 4-5pm, BA 3234 (CDF help centre)

Fridays, 4-6pm in BA 3234 (CDF help centre) (with TA, starting July 7)

Newsgroup: ut.cdf.csc363h

Previous offerings of this course: Winter 2006; Fall 2005; Summer 2005; Winter 2005; Fall 2004.

Course description

Introduction to the theory of computability: Turing machines, Church.s thesis, computable and noncomputable functions, recursive and recursively enumerable sets, reducibility. Introduction to complexity theory: models of computation, P, NP, polynomial time reducibility, NP-completeness, further topics in complexity theory. [26L, 13T]
Exclusion: CSC364H1, CSC365H1.
Prerequisite: CSC236H1/238H1/CSC240H1; CGPA 3.0/enrolment in a CSC subject POSt.
NOTE: Although the courses CSC363H1 and CSC373H1 can be taken in any order, we recommend that CSC373H1 be taken first.

Course Links

• Course information sheet in postscript or PDF
• Announcements (updated periodically, please read regularly)
• Course outline
• Lecture schedule and assigned readings
• Weekly tutorial exercises
• Assignments
• Test information
• Marks
• Remarking instructions and form