CSC C63 – Computability and Computational Complexity

  Winter 2018






Instructor: Michael Molloy

office: IC470
phone: 416-287-7255
office hours:  Friday April 20  11:00 - 12:30,  2:00 - 4:30

email: molloy@cs.toronto.edu

Text:

You can use either of the following two books.  Some comments to help you choose.


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

The Nature of Computation, by C. Moore and S. Mertens

      

Syllabus:

Click Here for the syllabus.

  

Policies:

UTSC Medical Certificate
Plagiarism
  (updated Jan 18)

 

Announcements:

The week before the final exam, I have office hours:
 
Friday
April 20  11:00 - 12:30,  2:00 - 4:30                                                                

Lectures:

Lecture Schedule


Assignments:

Assignment 1

Assignment 2
Assignment 3
Assignment 4 is due on Wed April 4 at 11:00 PM.    There was a typo in Problem 1a). K should be T.  It is now corrected.

Submit using MarkUs  


Old Tests:

2015 Midterm
2016 Midterm
 
2018 Midterm solutions

2015 Final Exam

2016 Final Exam  In 2018 we did not cover the material for problem 1(f).

Notes: