Computer Science
Computational Complexity: COMPSCI 750
Taught: Second semester, three lectures per week
Prerequisites: CompSci 320 or CompSci 350 or equivalent
Assessment: 60% exam; 20% test; 20% assignments
Lecturers:
Professor
Andre Nies. Room 303-421
Description: This is a survey paper on computational and descriptive complexities and applications.
Content: Turing machines, the classes P and NP, Cook-Levin Theorem, NP-completeness, Space complexity, Intractability, Randomized algorithms, Boolean circuits, Quantum Computing.
Archived material: Calude's 2016 Time complexity slides, Calude's 2016 Quantum computing slides.
Highly recommended for all graduate students interested in theoretical computer science.
Please check the CANVAS course page for more information.
-
Related Programmes