Languages

and the

Theory of

Computation

Fall 2019

- home
- syllabus
- resources
- class notes
- assignments

```
time: Tues/Thurs 10:00am - 11:30am
place: Sci 217
level: advanced
credits: 4
faculty: Jim Mahoney & Matt Ollis
text: Introduction to the Theory of Computation, 2nd Edition,
Michael Sipser, ISBN 8131501620
e.g. http://www.amazon.com/dp/8131501620
```

A mathematical introduction to the theory of computation. Topics include automata such as Turing machines, formal languages such as context-free grammar, and computability questions as described by "NP-complete" problems and Godel's incompleteness theorem. This is an upper-level course that presents the foundations of theoretical computer science. Expect practice with lots of mathematical proofs, with programming examples to build intuition. Prerequisite: Formal mathematics and programming experience

Here is an approximate schedule. The interests and abilities of the class may steer us in a different direction; we'll see.

```
1 math and programming preliminaries
2 finite automata
3 regular languages
4 context-free grammars
5 pushdown automata
6 Turing machines
7 what is an algorithm
8 decidable languages
9 the halting problem
10 reducibility
11 P and NP
12 NP-completeness
13 course round-up
```

- Week -5: Chapter 7: P vs NP.
- Week -4: Philosophy of Mind and 6.1, 6.2 and 6.4.
- Week -3: 10.1, 10.2 and 10.5 and maybe 10.4.
- Weeks -2 and -1: Individual choice.

https://cs.marlboro.college /cours /fall2019 /formal_languages /syllabus

last modified Thu February 29 2024 9:20 am

last modified Thu February 29 2024 9:20 am