Foundations of Computation
Carol Critchlow, Hobart and William Smith Colleges
David Eck, Hobart and William Smith Colleges
Pub Date: 2011
Conditions of Use
The particular mix of curricular topics is somewhat unconventional. The content choices reduce the potential utility of this book for existing courses (e.g., discrete math, theory of computation). However, this particular design may serve as a... read more
This is a good introductory book. In terms of coverage, I would like to see less logic and discrete math. A shorter review of logic, sets, functions and relations would be appropriate for a computational theory class. Normally discrete math and... read more
The text covers all areas and ideas of the subject appropriately, missing only the last portion of the NP problem that is discussed in my class (CSCI 3102: Introduction to the Theory of Computation). Beginning chapters are very thorough;... read more
Table of Contents
- 1 Logic and Proof
- 2 Sets, Functions, and Relations
- 3 Regular Expressions and FSA's
- 4 Grammars
- 5 Turing Machines and Computability
About the Book
Foundations of Computation is a free textbook for a one-semester course in theoretical computer science. It has been used for several years in a course at Hobart and William Smith Colleges. The course has no prerequisites other than introductory computer programming. The first half of the course covers material on logic, sets, and functions that would often be taught in a course in discrete mathematics. The second part covers material on automata, formal languages, and grammar that would ordinarily be encountered in an upper level course in theoretical computer science.
About the Contributors
Carol Critchlow, Associate Professor, Department of Mathematics and Computer Science, Hobart and William Smith Colleges. Critchlow received her PhD in Applied Mathematics from Cornell University in 1991 and joined the faculty of Hobart and William Smith Colleges the same year.
David J. Eck, PhD in Mathematics, Brandeis University, 1980. Professor, Department of Mathematics and Computer Science, Hobart and William Smith Colleges, Geneva, New York.