Theory of Computation

3 credit hours · Undergraduate

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