Theory of Computation

3 credit hours · Graduate

An advanced course in some of the fundamental theoretical concepts in computing science. Students will be introduced to the concepts of decidable, P, NP, NP-complete, and NP-hard problems. Two classes of languages of interest to computing scientists, namely, regular and context free languages, and corresponding automata for recognizing these languages, will also be studied. A brief discussion on the semantics of programming languages will be included. The concept of automata will be further extended using Turing machines. Turing machines will be used to explore the concept of decidability along with examples of decidable and undecidable problems.