About

CENG 512

Advanced Theory of Computation

This course will begin by explaining the different models of computation. It will then address the Church-Turing thesis. The course also will cover the topics of decidability and reducibility. Finally, detailed information is provided about complexity and related concepts.

Topics
Introduction and Overview
Math Review
Finite Automata and Regular Languages
Context-Free Languages and Pushdown Automata
Turing Machines and the Church-Turing Thesis
Decidability
Catch-up and review
Reducibility
Time complexity, P, and NP
NP-completeness
Catch-up and review
Space complexity
Randomization
Parallel complexity