CMSI 583 - Theory of Computation
Home Page and Course Syllabus - fall, 2008
Brief contents
- Class Meetings and Personnel
- Lectures: Monday evenings - 6:30-9:30 pm - Doolan Hall 219
- Lecturer: Philip Dorin - Doolan 102 - (310) 338-2832 - pdorin@lmu.edu
- Office hours: M 3-5, W 11-2, R 11-12, and by appointment
- Secretary: Jacqi Davis - Doolan 101 - (310) 338-7351 - JaDavis@lmu.edu
- Objectives
- The goal is to become familiar with some of the main ideas in the theory of computation. After some preliminary
mathematics (cardinality, proof techniques, alphabets, strings, and languages), we will talk about regular expressions
and finite automata; context-free grammars, pushdown automata, and their relation to parsing; Turing machines, the
Church-Turing hypothesis, problem reductions, undecidable problems and non-computable functions; intractability, P vs. NP, Cook's theorem, and NP-completeness.
- Prerequisites
- You must know how to program in some high-level language.
- You should be reasonably comfortable reading, and constructing some, formal proofs.
- Textbooks
- Hopcroft, Ullman, and Motwani. Introduction to Automata Theory, Languages, and Computation (3rd edition). Addison-Wesley, 2007.
- Garey and Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979.
Classic introduction to NP-completeness, including an exhaustive appendix of NP-complete problems.
- References
- Crossley, Ash, Brickhill, Stillwell, and Williams. What is Mathematical Logic? Dover Publications, 1990. A skinny
little book with six excellent lectures including an historical survey of the subject, completeness of the predicate calculus,
model theory, Turing machines, Godel's theorems, and set theory.
- Halmos. Naive Set Theory. Springer-Verlag, 1974. A(nother) skinny little book that develops the main ideas of
set theory in twenty-five concise, very readable lectures.
- Hey and Allen (eds.) The Feynman Lectures on Computation. Addison-Wesley, 1996. Computation from Feynman's
typically unique, but not always easy-to-understand, point of view, including discussions of computability, coding and information
theory, the thermodynamics of computing, and quantum mechanical computation.
- Kohavi. Switching and Finite Automata Theory (2nd edition). McGraw-Hill, 1978. A well-known, highly-readable
text that covers combinational logic, switching theory, and the theory of finite-state machines.
- Kozen. Automata and Computability. Springer, 1997. An alternative to Hopcroft et al., organized as a sequence
of lectures.
- Linz. An Introduction to Formal Languages and Automata (third edition). D. C. Heath, 2001. This was once
the textbook for CMSI 385, and is a slightly simplified version of the corresponding chapters of Hopcroft et al.
- Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, 1967. A classic, entertaining book that covers a lot of the
course material from a slightly different angle.
- Papadimitriou. Computational Complexity. Addison-Wesley, 1994. A comprehensive treatment of computability,
logic, and complexity that picks up where (the textbook for) this course leaves off.
- Sipser. Introduction to the Theory of Computation. PWS Publishing, 1997. Another former CMSI 385 text, covering virtually the same material as Hopcroft et al.
- Coursework
- A set of highly recommended homework problems will be issued at each class, but it is generally not collected/graded. Typically, solutions are discussed,
or distributed, at the next class meeting.
- There will be a final exam on Monday evening, December 8.
Revised: August 25, 2008