Theory of Computation

A branch of computer science that deals with whether and how efficiently problems can be solved on a computer. It is divided into two major sub-branches: computability theory and complexity theory, but both sub-branches deal with formal models of computation.

All categories

Books under this sub-category (23 books)

Introduction to Theory of Computation

Post date: 29 Apr 2016
A free textbook for an undergraduate course on the Theory of Computation at Carleton University.
Publication date: 11 Apr 2016
License: Creative Commons Attribution-ShareAlike 4.0 International
 
 Introduction to Theory of Computation

Introduction to Theory of Computation

Post date: 29 Apr 2016
A free textbook for an undergraduate course on the Theory of Computation at Carleton University.
Publication date: 11 Apr 2016
License: Creative Commons Attribution-ShareAlike 4.0 International


Algorithm and Complexity

Post date: 30 Oct 2004
Methods for solving problems on computers and the costs (usually the running time) of using those methods.
Publisher: A K Peters, Ltd.
Publication date: 09 Dec 2002
 
Algorithm and Complexity

Algorithm and Complexity

Post date: 30 Oct 2004
Methods for solving problems on computers and the costs (usually the running time) of using those methods.
Publisher: A K Peters, Ltd.
Publication date: 09 Dec 2002


An Introduction to Computing

Post date: 26 Feb 2007
Introduces the basics of the functional and imperative models of computation, recursive and iterative processes, and the basics of programming using higher-order functions. Uses Standard ML and Java as the programming languages.
Publication date: 02 Aug 2003
 
An Introduction to Computing

An Introduction to Computing

Post date: 26 Feb 2007
Introduces the basics of the functional and imperative models of computation, recursive and iterative processes, and the basics of programming using higher-order functions. Uses Standard ML and Java as the programming languages.
Publication date: 02 Aug 2003


An Introduction to the Theory of Computation

Post date: 12 Dec 2006
This book explores terminologies and questions concerning programs, computers, problems, and computation. The exploration reduces in many cases to a study of mathematical theories, such as those of automata and formal languages.
Publisher: Computer Science Press
Publication date: 31 Dec 1989
 
An Introduction to the Theory of Computation

An Introduction to the Theory of Computation

Post date: 12 Dec 2006
This book explores terminologies and questions concerning programs, computers, problems, and computation. The exploration reduces in many cases to a study of mathematical theories, such as those of automata and formal languages.
Publisher: Computer Science Press
Publication date: 31 Dec 1989


Approximation Algorithms

Post date: 19 Sep 2007
This book covers the dominant theoretical approaches to the approximate solution of hard combinatorial optimization and enumeration problems.
Publisher: Springer-Verlag GmbH
Publication date: 01 Jan 2003
Document Type: Book
 
Approximation Algorithms

Approximation Algorithms

Post date: 19 Sep 2007
This book covers the dominant theoretical approaches to the approximate solution of hard combinatorial optimization and enumeration problems.
Publisher: Springer-Verlag GmbH
Publication date: 01 Jan 2003
Document Type: Book


Building Blocks for Theoretical Computer Science (Version 1.3)

Post date: 11 May 2016
This book teaches you how to read and write mathematical proofs. It also gives a brief introduction to some key topics in theoretical computer science: algorithm analysis and complexity, automata theory, and computability.
Publication date: 01 Jan 2013
 
Building Blocks for Theoretical Computer Science (Version 1.3)

Building Blocks for Theoretical Computer Science (Version 1.3)

Post date: 11 May 2016
This book teaches you how to read and write mathematical proofs. It also gives a brief introduction to some key topics in theoretical computer science: algorithm analysis and complexity, automata theory, and computability.
Publication date: 01 Jan 2013


Combinatorial Algorithms

Post date: 08 Sep 2005
These lecture notes cover algorithms, especially combinatorial algorithms, with the main goal of creating correct and always-efficient ones.
Publication date: 31 Jan 2015
License: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International
Document Type: Book
 
Combinatorial Algorithms

Combinatorial Algorithms

Post date: 08 Sep 2005
These lecture notes cover algorithms, especially combinatorial algorithms, with the main goal of creating correct and always-efficient ones.
Publication date: 31 Jan 2015
License: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International Document Type: Book


Combinatorial Optimization: Exact and Approximate Algorithms

Post date: 23 Oct 2016
Lecture notes from the class CS261: Optimization and Algorithmic Paradigms taught at Stanford. They cover topics in approximation algorithms, exact optimization, and online algorithms.
Publication date: 11 Mar 2011
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported
Document Type: Lecture Notes
 
Combinatorial Optimization: Exact and Approximate Algorithms

Combinatorial Optimization: Exact and Approximate Algorithms

Post date: 23 Oct 2016
Lecture notes from the class CS261: Optimization and Algorithmic Paradigms taught at Stanford. They cover topics in approximation algorithms, exact optimization, and online algorithms.
Publication date: 11 Mar 2011
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported Document Type: Lecture Notes


Complexity of Algorithms

Post date: 09 Dec 2006
These notes deal with the foundations of measuring the complexity of a problem, algorithm or structure used in computer science, the traditional branches of mathematics, statistical physics, biology, medicine, social sciences and engineering.
Publication date: 31 Dec 1999
 
Complexity of Algorithms

Complexity of Algorithms

Post date: 09 Dec 2006
These notes deal with the foundations of measuring the complexity of a problem, algorithm or structure used in computer science, the traditional branches of mathematics, statistical physics, biology, medicine, social sciences and engineering.
Publication date: 31 Dec 1999


Complexity Theory

Post date: 21 Mar 2007
These set of introductory notes give the broad picture of modern complexity theory, define the basic complexity classes and give some examples of each complexity class.
Publication date: 06 Dec 1999
 
Complexity Theory

Complexity Theory

Post date: 21 Mar 2007
These set of introductory notes give the broad picture of modern complexity theory, define the basic complexity classes and give some examples of each complexity class.
Publication date: 06 Dec 1999


Complexity Theory: A Modern Approach

Post date: 21 Oct 2006
A draft of a textbook on computational complexity theory. Covers basic complexity classes, lowerbounds for concrete computational models, and some advanced topics.
Publisher: Cambridge University Press
Publication date: 20 Apr 2009
Document Type: Textbook
 
Complexity Theory: A Modern Approach

Complexity Theory: A Modern Approach

Post date: 21 Oct 2006
A draft of a textbook on computational complexity theory. Covers basic complexity classes, lowerbounds for concrete computational models, and some advanced topics.
Publisher: Cambridge University Press
Publication date: 20 Apr 2009
Document Type: Textbook


Computation Complexity

Post date: 21 Mar 2007
These notes deal with the foundations of complexity theory for a one-semester graduate course. Part of it is also suitable for an undergraduate course, at a slower pace. Mathematical maturity is the main prerequisite.
Publication date: 15 Mar 1994
Document Type: Lecture Notes
 
Computation Complexity

Computation Complexity

Post date: 21 Mar 2007
These notes deal with the foundations of complexity theory for a one-semester graduate course. Part of it is also suitable for an undergraduate course, at a slower pace. Mathematical maturity is the main prerequisite.
Publication date: 15 Mar 1994
Document Type: Lecture Notes


Computational Complexity: A Conceptual Perspective (Draft)

Post date: 27 Oct 2006
Focuses on the high level study of computation, exploring the connections among computational problems and notions. Covers theory of NP-completeness, approximation, probabilistic proof systems, pseudorandomness and cryptography.
Publisher: Cambridge University Press
Publication date: 28 Apr 2008
Document Type: Book
 
Computational Complexity: A Conceptual Perspective (Draft)

Computational Complexity: A Conceptual Perspective (Draft)

Post date: 27 Oct 2006
Focuses on the high level study of computation, exploring the connections among computational problems and notions. Covers theory of NP-completeness, approximation, probabilistic proof systems, pseudorandomness and cryptography.
Publisher: Cambridge University Press
Publication date: 28 Apr 2008
Document Type: Book


CS 373: Introduction to Theory of Computation

Post date: 20 Oct 2016
A collection of class notes used in teaching CS 373 (Theory of Computation), in the Computer Science department in University of Illinois at Urbana-Champaign.
Publication date: 18 May 2009
License: Creative Commons Attribution-NonCommercial 3.0 Unported
Document Type: Lecture Notes
 
CS 373: Introduction to Theory of Computation

CS 373: Introduction to Theory of Computation

Post date: 20 Oct 2016
A collection of class notes used in teaching CS 373 (Theory of Computation), in the Computer Science department in University of Illinois at Urbana-Champaign.
Publication date: 18 May 2009
License: Creative Commons Attribution-NonCommercial 3.0 Unported Document Type: Lecture Notes


Essentials of Theoretical Computer Science

Post date: 30 Sep 2006
Covers the basics of the theory of computation and provides some of the tools used in program verification, translation and compiling, and the analysis of algorithms.
Publication date: 31 Dec 1996
Document Type: Textbook
 
Essentials of Theoretical Computer Science

Essentials of Theoretical Computer Science

Post date: 30 Sep 2006
Covers the basics of the theory of computation and provides some of the tools used in program verification, translation and compiling, and the analysis of algorithms.
Publication date: 31 Dec 1996
Document Type: Textbook


Book Categories
Sponsors