Introduction to the theory of computability: Turing machines, Church's thesis, computable and non-computable 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.
Instructor: Vincent Maccio
Monday: 1:00pm-3:00pm, Thursday: 4:00pm-5:45pm
The course syllabus can be found here. A quick note about assignment due dates. All assignment due dates on the syllabus are placeholders. The actual due date will depend on how fast we proceed through the material. I will always give you at least two weeks to complete an assignment, from the time it's posted until the due date.
This course uses Piazza as its discussion board, the course can be found here, the access code is csc363h5s.