Foundations of Computation
Carol Critchlow, Hobart and William Smith Colleges
David Eck, Hobart and William Smith Colleges
Pub Date: 2011
Conditions of Use
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 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; re-explaining neatly the basic technical words that will be coming in latter chapters. It has some Python programming code in it, so that is a plus. But it has fewer diagrams and problems about PDAs, NFAs, and DFAs than the current book that we are using (Sipser).
I did not find any inaccuracies.
The text is by-and-large up-to-date. But then again, this topic is mature having been formulated and formalized in the 1930s through the 1960s.
The writing is easy and clear. The author uses second person perspective to explain things which makes the book interactive.
It is quite good.
The book is, in fact, easy to subdivide into smaller modules. It will be easy to re-organize the course content if and when time becomes an issue (common around here because of the threat of hurricanes during the storm season).
Topics are presented in a suitable manner. However, FSAs are introduced a tad too late for my taste. And, as mentioned before, there are only a limited number of PDA, FSA, NFA problems.
No noticeable interface issues were encountered.
No grammatical errors were found.
As a textbook about the Theory of Computation, this criterion is marginally relevant. That being said, there were no obvious references to race, ethnicity, or background.
I am happy that this book is available on an "open" basis. At the very least, this book could serve as a good reference and balancing tool for students enrolled in my CSCI 3102 classes. I am willing to even adopt it as a primary textbook after this Spring 2017 semester where I have already made arrangements to use Sipser for the course.
Table of Contents
- Chapter 1: Logic and Proof
- Chapter 2: Sets, Functions, and Relations
- Chapter 3: Regular Expressions and FSA's
- Chapter 4: Grammars
- Chapter 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.