01 / Reading Guide
Reading Guide
Who this book is for
For graduate students and strong undergraduates seeking a broad formal treatment of computing beyond introductory automata. The book emphasizes concrete computational models and the resources they consume. Its route is particularly useful when readers want to connect circuit descriptions, machines with memory and architectural constraints within a single theoretical framework.
Prerequisites
Computer organization, discrete mathematics and confidence with proofs are recommended. Review Boolean logic, graphs, asymptotic analysis and induction. An initial algorithms course helps with the complexity and resource-tradeoff arguments.
What it covers
Logic circuits and machines with memory lead into automata, computability, algebraic circuits and parallel computation. Later chapters develop complexity classes, circuit complexity, space-time tradeoffs, memory hierarchies and VLSI models. The organizing question is how a model’s restrictions shape what can be computed and at what resource cost.
How to use it
Choose a small problem and specify its input size before comparing two computational models. Draw the circuit or machine state explicitly and count the resources that the selected model measures. Reconstruct a simulation argument, stating where the overhead arises. For a lower bound, identify which assumptions make the argument possible and why changing the model might invalidate it. Keep examples from memory hierarchies separate from unrestricted machine claims, and use exercises to practise these distinctions.
Edition and sources
The author’s complete electronic release derives from the 1998 Addison-Wesley book and corrects known errors. Rights reverted to Savage; the site specifies CC BY-NC-ND 3.0 US for the July 2008 electronic release. That release date is distinct from original publication and from later site updates.
