Elements of the Theory of Computation, 2nd Edition
©1998 |Pearson | Available
Christos H. Papadimitriou, University of California-Berkeley
©1998 |Pearson | Available
Appropriate for senior and graduate level courses in Computer Science Theory, Automata, and Theory of Computation.
This is the long awaited Second Edition of Lewis and Papadimitriou's best-selling theory of computation text. In this substantially modified edition, the authors have enhanced the clarity of their presentation by making the material more accessible to a broader undergraduate audience with no special mathematical experience.
Would you like a theory of computation text that provides a solid, specialized introduction to algorithms?
Introduces asymptotic analysis and O- notation.
Truncates long proofs and presents them as exercises.
Provides problems after each section to check student comprehension.
Includes extensive discussion of state minimization, the Myhill-Nerode Theorem, string matching, and parsing.
Many combinatorial problems are introduced and analyzed (including variants of satisfiability), and their apparent complexity contrasted.
Would you like to teach NP—completeness, as well as ways of coping with it, in your course?
Extensive section on coping with NP - completeness that covers special cases, approximation algorithms, backtracking, and local search heuristics.
Covers NP - completeness including state minimization problem of nondeterministic finite automata.
Logic coverage has been limited to propositional logic in relation to NP - completeness.
Considers Cook's Theorem again via the tiling problem.
Discusses approximation and its complexity.
Uses the terms recursive and recursively innumerably.
Quantitatively analyzes simulations between machine models.
Introduces and analyzes a model of random access Turing machines, similar to RAMs.
Uses random access Turing machines to bridge the “credibility gap” between Turing machine model and the empirical concept of an algorithm.
Includes some recursion theory (up to Rice's theorem).
Provides an informal, concise development of A-recursive functions.
1. Sets, Relations, and Languages.
2. Finite Automata.
3. Context-free Languages.
4. Turing Machines.
6. Computational Complexity.
Bridge Page t/a A First Course
Ullman & Widom
Pearson offers affordable and accessible purchase options to meet the needs of your students. Connect with us to learn more.
K12 Educators: Contact your Savvas Learning Company Account General Manager for purchase options. Instant Access ISBNs are for individuals purchasing with credit cards or PayPal.
Savvas Learning Company is a trademark of Savvas Learning Company LLC.
We're sorry! We don't recognize your username or password. Please try again.
The work is protected by local and international copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning.
You have successfully signed out and will be required to sign back in should you need to download more resources.