CSC C63 – Computability and Complexity


Instructor:

Michael Molloy

office: IC470
phone: 416-287-7255
office hours:  see below for exam period hours
email: molloy@cs.toronto.edu


Office hours during exam period:

  
I am in my office  on Mon April 9.

I will be in my office on the afternoon of Thur April 19.

I will be in my office on the afternoons of Mon April 23 and Wed April 25.  Send email for an appointment, or if you just drop in sometime before 4:00  you'll probably find me. 

Nick will hold office hours on Friday April 27 11am-2pm in IC348.

Text:

Introduction to the Theory of Computation, by M. Sipser. 2nd edition.

      

Syllabus:

Click Here for the syllabus.

  

Policies:

Doctor’s notes    UTSC Medical Certificate
Plagiarism

     

Announcements:

 The Clay Mathematics Institute will pay you $1,000,000 if you can prove whether P=NP.

 

 Midterm Solutions

      

Lectures:

Lecture Schedule

Assignments:

Assignment 1  is due on Tue, Jan 31 at 3:00 in the course dropbox. 

 

Assignment 2 is due on Wed, Feb 15 at 11:00 AM in the dropbox.


Assignment 3 is due on Mon, Mar 5 at 11:00 AM in the dropbox.


Assignment 4 is due on Wed, Mar 21 at 11:00 AM in the dropbox.


Assignment 5 is due on Wed, Apr 4 at 11:00 AM in the dropbox. 



Old Tests:

 2008 Midterm    Solutions
2011 Midterm

Practice Problems on decidability and recognizability

2008 Final Exam
2011 Final Exam

Notes:   

Two descriptions of the proof that PRIME is in NP
More info on RSA