Introduction to Theoretical Computer Science

Boaz Barak

Work in progress

These is a textbook in preparation for an introductory undergraduate course on theoretical computer science. I am using this text for Harvard CS 121.

You can also download all chapters in a single PDF file (about 500 pages, 10MB).

See this website for (a very much work in progress) implementation of the NAND* programming languages that are used in in these notes.

If you have any comments, suggestions, typo fixes, etc.. I would be very grateful if you post them as an issue or pull request in the GitHub repository where I am maintaining the source files for these notes.


Preface ( pdf version)

0 Introduction ( pdf version)

1 Mathematical background ( pdf version)

2 Representation ( pdf version)

3 Defining computation ( pdf version)

4 Syntactic sugar, and computing every function ( pdf version)

5 Code and data ( pdf version)

6 Programs with loops ( pdf version)

7 Universality and indirection ( pdf version)

8 Other models ( pdf version)

9 Uncomputability ( pdf version)

10 Restricted computational models ( pdf version)

11 Gödel’s Incompleteness Theorem ( pdf version)

12 Efficient algorithms ( pdf version)

13 Formally defining running time ( pdf version)

14 Polynomial-time reductions ( pdf version)

15 NP, NP completeness, and the Cook-Levin Theorem ( pdf version)

16 What if P=NP? ( pdf version)

17 Review of probability ( pdf version)

18 Randomized algorithms ( pdf version)

19 Modelling probabilistic computation ( pdf version)

20 Cryptography ( pdf version)

21 Proofs and algorithms ( pdf version)

22 Quantum computing ( pdf version)

A. The NAND programming language (appendix Jupyter notebook) ( pdf version)

Copyright 2018, Boaz Barak.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

HTML version is produced using the Distill template, Copyright 2018, The Distill Template Authors.