Introduction to the Theory of Computation
Description
In this introductory course on theory of computation, students will be asked to find solutions to several computational questions - ranging from how computation is defined to how problems can be efficiently solved through these models. Some of these questions can be answered completely and some questions lead to major open problems in computer science and mathematics today. By the end of this course, students will be able to classify computational problems in terms of their computational complexity. Students will also gain a deeper appreciation for some of the fundamental issues in computing that are independent of technology trends.
Prerequisites
Topics include
- Regular sets: finite automata, regular expressions, equivalences among notations, methods of proving a language not to be regular
- Context-free languages: grammars, pushdown automata, normal forms for grammars, proving languages non-context-free
- Turing machines: equivalent forms, undecidability
- Nondeterministic Turing machines: properties, the class NP, complete problems for NP, Cook's theorem, reducibilities among problems
Course Availability
The course schedule is displayed for planning purposes – courses can be modified, changed, or cancelled. Course availability will be considered finalized on the first day of open enrollment. For quarterly enrollment dates, please refer to our graduate education section.
