Course syllabus
COURSE DETAILS
This is a survey paper on computational and descriptive complexities and applications.
It discusses Turing machines, the complexity classes P and NP, Cook-Levin Theorem, NP-completeness, space complexity, BPP and randomised algorithms, and special topics on quantum computing.
LECTURES:
Mo 3:00PM - 4:00PM 303-B09 (Sci Maths & Physics, Room B09)
We 3:00PM - 4:00PM 260-213 (Owen G Glenn, Room 213)
Fr 3:00PM - 4:00PM 114-G14 (Commerce A, Room G14)
(Probably no lectures in Week 6. Also on Tue Oct 17 instead of Fri Oct 20.)
TEACHING STAFF
Office 303-421
andre@cs.auckland.ac.nz
Office hours: Tue 2:00-3:30
Class Rep: Yan Kolezhitskyi, ykol002@aucklanduni.ac.nz
Text required: Michael Sipser, Introduction to the theory of computation, 2d or 3d edition
ISBN13: 978-1-133-18779-0
ASSESSMENT
60% exam; 20% test; 20% assignments
Course summary:
| Date | Details | Due |
|---|---|---|