CS 6041:Theory of Computation

3 Class Hours 0 Laboratory Hours 3 Credit Hours
Prerequisite: CS 5070
Courses that may be taken concurrently:
CS 5040
This course covers theoretical topics of computer science including automata, formal languages (such as regular and context-free languages), grammars, Turing machines, algorithms, nondeterminism, computability, decidability, and complexity. Topics also include intractable and NP-complete problems for graphs (such as TSP, Node Cover, Hamiltonian Circuit, Independent Set) and polynomial reducibility.