Theory of Computation Lectures
This note covers the following topics: Sets, functions and other preliminaries, Formal Languages, Finite Automata , Regular Expressions, Turing Machines, Context-Free Languages, Rice's Theorem, Time complexity, NP-Completeness, Space Complexity , Log Space, Oracle machines and Turing Reducibility, Probabilistic Complexity, Approximation and Optimisation, Complexity Hierarchy Theorems.
Author(s): UNSW Sydne
NA Pages 
Theory of Computation by Frank Stephan
This note explains the following topics: sets and regular expressions, Grammars and the chomsky hierarchy, Finite automata, Nondeterministic finite automata, Combining languages, Normal forms and algorithms, Deterministic membership testing, Nondeterministic membership testing, Models of computation, Complexity considerations, Undecidable problems, Undecidability and formal languages.
Author(s): Frank Stephan
176 Pages
Theory of Computation by Kyle Burke
This pdf begins with an overview of resources, organization and motivation and preview of CS theory covering the Limits of Computation, the Undecidability of the Halting Problem.The Automata and Machines including Deterministic and Nondeterministic Finite-state Automata, Pushdown Automata, and Turing Machines and Language Classes. Finally focus shifts to Computational Complexity, discussing NP-Completeness, Approximation Algorithms, and the Hardness of Approximation.
Author(s): Kyle Burke
114 Pages
Theory of Computation by Jim Hefferon
This PDF covers the following topics related to Theory of Computation : Mechanical Computation, Background, Languages and graphs, Automata, Computational Complexity.
Author(s): Jim Hefferon
439 Pages
Models of Computation by John E. Savage
This PDF Models of Computation by John E. Savage covers the following topics related to Computation Theory : The Role of Theory in Computer Science, General Computational Models, Logic Circuits, Machines with Memory, Finite-State Machines and Pushdown Automata, Computability, Algebraic and Combinatorial Circuits, Parallel Computation, Computational Complexity, Complexity Classes, Circuit Complexity, Space–Time Tradeoffs, Memory-Hierarchy Tradeoffs, VLSI Models of Computation.
Author(s): John E. Savage, Brown University
698 Pages
Lecture Notes Theory of Computation
This note covers the following topics: Properties of binary operations, Concantenation properties, Finite automata, Formal Languages, Pumping Lemma.
Author(s): S R Engineering College
155 Pages
Advanced Theory in Computation
This note covers the following topics: Analysis of Algorithms, String Matching, Amortized Analysis, Knuth-Morris-Pratt Algorithm, Pattern-Matching Machine, Boyer-Moore Algorithm, Horspool Algorithm, Suffix Trees, Dictionary Techniques, Ziv-Lempel Coding, Randomized Algorithms, Reservation-Price-Policy, Portfolio Selection, Statistical Adversaries.
Author(s): Seoul National University
NA Pages
