Theory of Computation by Kyle Burke

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

Introduction to Computational Theory Lecture Notes

This note covers the following topics: Languages, Finite Automata, Regular Languages and Sets, Context-Free Grammars, Pushdown Automata and Context-Free Languages, Turing Machines, The Chomsky Hierarchy, P and NP.

Author(s): BYU Computer Science Department

NA 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

Notes on Computation Theory

This course is an introduction to the Theory of Computation. Topics covered includes: Background Mathematics, Models of Computation, Context-Free Grammars, Automata, The Chomsky Hierarchy.

Author(s): Konrad Slind

231 Pages

Notes on Computational Complexity Theory

This note provides an introduction to the theory of computational complexity. Topics covered includes: Models of computation, Time and space complexity classes, Nonterminism and NP, Diagonalization, Oracles and relativization, Alternation, Space complexity, Natural proofs, Randomized classes, Counting classes, Descriptive complexity and Interactive proofs.

Author(s): James Aspnes

180 Pages

Theory Of Computation Lecture Notes

This lecture note covers the following topics: Theory Of Computation, Introduction To Automata, Finite Automata, Regular Expressions And Languages, Properties Of Regular Language, Context-free Grammars And Languages, Applications Of Context-free Grammars, Pushdown Automata, Properties of Context-Free Languages.

Author(s): Prof. D. Chandrasekhar Rao, Prof. Kishore Kumar Sahu and Prof. Pradipta Kumar Das

120 Pages

Introduction to theory of computation by Tom Carter

This note explains the following topics: Symbols, strings and languages, Finite automata, Regular expressions and languages, Markov models, Context free languages, Language recognizers and generators, The Chomsky hierarchy, Turing machines, Computability and actability, Computational complexity.

Author(s): Tom Carter

76 Pages

The Theory of Languages and Computation

This note covers the following topics: Automata, Set Theory, The Natural numbers and Induction, Foundations of Language Theory, Operations on Languages, Deterministic Finite Automata, Formal Languages, Computability, Computations of Turing Machines, The Primitive Recursive Functions, The Partial Recursive Functions, DNA Computing, Analog Computing and Scientific Computing.

Author(s): Jean Gallier and Andrew Hicks

109 Pages

Theory of Computation by S. Arun Kumar

This book covers the following topics: The RAM Model, The Primitive Recursive Functions, The Partial Recursive Functions, Coding and Godelization, The Hierarchy of Primitive Recursive Functions, Universality and Parametrisation, The type-free lambda calculus.

Author(s): S. Arun Kumar

83 Pages

Computation Theory Lecture notes

The aim of this course note is to introduce several apparently different formalisations of the informal notion of algorithm; to show that they are equivalent; and to use them to demonstrate that there are incomputable functions and algorithmically undecidable problems.

Author(s): Prof Anuj Dawar

93 Pages