CS 475
CS 475 - Formal Models of Computation
Fall 2023
Title | Rubric | Section | CRN | Type | Hours | Times | Days | Location | Instructor |
---|---|---|---|---|---|---|---|---|---|
Formal Models of Computation | CS475 | C3 | 35887 | LCD | 3 | 1530 - 1645 | T R | 1214 Siebel Center for Comp Sci | Mahesh Viswanathan |
Formal Models of Computation | CS475 | C4 | 35895 | LCD | 3 | 1530 - 1645 | T R | 1214 Siebel Center for Comp Sci | Mahesh Viswanathan |
Formal Models of Computation | MATH475 | C3 | 35897 | LCD | 3 | 1530 - 1645 | T R | 1214 Siebel Center for Comp Sci | Mahesh Viswanathan |
Formal Models of Computation | MATH475 | C4 | 35903 | LCD | 3 | 1530 - 1645 | T R | 1214 Siebel Center for Comp Sci | Mahesh Viswanathan |
See full schedule from Course Explorer
Official Description
Course Director
Text(s)
Primary Textbook: Theory of Computation by Dexter Kozen
For Background and Additional Topics: Automata and Computability by Dexter Kozen
Learning Goals
[1] Recognize regular and non-regular languages (1), (6)
[2] Prove recursive/recursive enumerability of sets (1), (6)
[3] Prove problems to be undecidable/non-recursively enumerable through reductions (6)
[4] Understand the relationship between complexity classes (6)
[5] Prove that a problem belongs to a certain complexity class (1)
[6] Prove that a problem is the hardest in a complexity class through reductions (6)
[7] Understand the power of nondeterminism in a computational setting (6)
[8] Understand the power of randomization in a computational setting (6)
Topic List
Automata Theory:
- Deterministic/nondeterminstic finite automata
- Regular languages
- 2-way automata, alternation
Recursion Theory:
- Turing machine and its variants
- Recursive enumerability and decidability
- Reductions
- Arithmetic Hierarchy
Complexity Theory
- Definitions of time and space bounded complexity, and classical complexity classes
- Relationship between complexity classes
- Alternation and randomization
- Interactive proofs