Introduction to the Theory of Computation

CS154

Stanford School of Engineering


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

CS103

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.

Thank you for your interest. The course you have selected is not open for enrollment. Please click the button below to receive an email when the course becomes available again.

Request Information