CSSE 474: Theory of Computation
Computer Science and Software Engineering
Rose-Hulman Institute of Technology
Catalog Course Description
Prerequisites: CSSE 230 and MA 375
Crosslisted as: MA474
Students study mathematical models by which to answer three questions:
What is a computer? What limits exist on what problems computers can
solve? What does it mean for a problem to be hard? Topics include
models of computation (including Turing machines), undecidability
(including the Halting Problem) and computational complexity
(including NP-completeness).
Course Outcomes
Students who successfully complete this course should be able to:
- Discuss the concept of finite state machines.
- Design a deterministic finite-state machine to accept a specified
language.
- Explain context-free grammars.
- Explain at least one algorithm for both top-down and bottom-up
parsing.
- Explain the Church-Turing thesis and its significance.
- Determine a language's location in the Chomsky hierarchy (regular
sets, context-free, context-sensitive, and recursively enumerable
languages).
- Prove that a language is in a specified class and that it is not
in the next lower class.
- Convert among equivalently powerful notations for a language,
including among DFAs, NFAs, and regular expressions, and between PDAs
and CFGs.
- Explain how some problems have no algorithmic solution.
- Provide examples that illustrate the concept of uncomputability.
- Define the classes P and NP.
- Explain the significance of NP-completeness.
- Prove that a problem is NP-complete by reducing a classic known
NP-complete problem to it.
Instructor
Michael Wollowski
Text
Our primary text is as follows. Readings and assignments will come
from it.
Michael Sipser. Introduction to the Theory of Computation, 2nd
ed. Thomson Course Technology, Boston, MA, USA, 2006.
For the materials covered in this course, it is a lot of times
useful to have an alternate presentation of the materials. Here are a
couple of texts you may wish to consult:
- John Martin. Introduction to Languages and the Theory of
Computation, 3rd ed. McGraw Hill, New York, NY, 2003.
- Daniel Cohen. Introduction to Computer Theory, 2nd ed. John
Wiley and Sons, Hoboken, NJ, 1997.
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introduction to
Automata Theory, Languages, and Computation, 2nd ed. Addison
Wesley, Boston, MA, 2001.
Topics
Below is a schedule which gives an ordering of the material we will
cover. The correspondence of the materials to weeks is very
approximate. You will notice that we are starting out with Turing
Machines. They are a very straight-forward concept and are a
tremendous aid in setting the agenda for this course.
| Week | Topics
|
| 1 | Skills review, Turing Machines
|
| 2 | Turing Machines, Church Turing Thesis, The Halting
Problem
|
| 3 | Regular languages
|
| 4 | Regular languages
|
| 5 | Context free languages
|
| 6 | Context sensitive languages
|
| 7 | Decidability
|
| 8 | Reducibility
|
| 9 | Complexity
|
| 10 | Tractable and intractable problems
|
Grading
There will be two exams and a final.
There will be about 10 homework assignments, containing assignments
from the book and other sources. Some of the homework assignments will
include tasks such as programming a Turing Machine, developing regular
expressions and context-free grammars for a subset of a programming
language and to understand Goedel's incompleteness proof.
Your final grade will be determined as follows:
| Exam 1 | 20%
|
| Exam 2 | 25%
|
| Final exam | 25%
|
| Homework | 25%
|
| Participation | 5%
|
More to come!