Great Ideas in Theoretical Computer Science Lecture Notes

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

Introduction to Theory of Computation Lecture Notes

This note explains the following topics: Discrete mathematics, Deterministic Finite Automata, Nondeterministic Finite Automata, Equivalence of DFA and NFA, Nondeterministic Finite Auotmata, egular expressions and finite automata, Non-regular languages and Pumping Lemma, Myhill-Nerode Theorem, Context-free languages and Ambiguity, Closure Properties, Pumping Lemma and non-CFLs, Closure Properties and non-CFL Languages, Decidable and Recognizable Languages.

Author(s): Mahesh Viswanathan

NA 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

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

Introduction to Theory of Computation

This is a free textbook for an undergraduate course on the Theory of Computation, which have been teaching at Carleton University since 2002.Topics covered includes: Finite Automata and Regular Languages, Context-Free Languages, Turing Machines and the Church-Turing Thesis, Decidable and Undecidable Languages and Complexity Theory.

Author(s): Anil Maheshwari and ichiel Smid

246 Pages

Introduction to Theoretical Computer Science or Theory of Computation

This note covers the following topics: introduction to theoretical computer science, language, regular language, finite automata, language accepted by dfa, nondeterministic finite automata, equivalence of nfa, regular language and fa, application of fa, nonregular languages, context free languages, turing machines, computability and complexity.

Author(s): Pavan Kumar Anumula, Andrea Di Fabio and Jia Zhu

NA 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

ConstructiveComputation Theory

This is an executable course note implemented in Pidgin ML, which is a core subset of the Objective Caml programming language under the so-called revised syntax.

Author(s): Gerard Huet

NA Pages

A Computational Introduction to Number Theory and Algebra (V. Shoup)

This book introduces the basic concepts from computational number theory and algebra, including all the necessary mathematical background. Covered topics are: Basic properties of the integers, Congruences, Computing with large integers, Euclid’s algorithm, The distribution of primes, Abelian groups, Rings, Finite and discrete probability distributions, Probabilistic algorithms, Probabilistic primality testing, Finding generators and discrete logarithms in Zp, Quadratic reciprocity and computing modular square roots, Modules and vector spaces, Matrices, Subexponential-time discrete logarithms and factoring, Polynomial arithmetic and applications.

Author(s): Victor Shoup

NA Pages