CS 483 Intro to Theory of Computation

This course is an introduction to the main theory and concepts in computation. The main topics include Turing machines, the Church-Turing thesis; decidability; halting problem; reducibility; undecidable problems; time classes; P, NP NP-complete; space classes; hierarchy theorems; probabilistic algorithms. Prerequisite: CS 341, CS 342

Credits

3

Prerequisite

Take CS 341 and CS 342;