Introduction to Theoretical Computer Science

Boaz Barak

Work in progress

This 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 550 pages, 12MB). See also the table of contents.

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 boazbk/tcs where I am maintaining the source files for these notes. You can also post comments on each chapter in the links below.


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 Other models ( pdf version)

8 Uncomputability ( pdf version)

9 Restricted computational models ( pdf version)

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

11 Efficient algorithms ( pdf version)

12 Formally defining running time ( pdf version)

13 Polynomial-time reductions ( pdf version)

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

15 What if P=NP? ( pdf version)

16 Space bounded computation ( 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 (Jupyter notebook appendix) ( pdf version)

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

C. Lambda calculus (Jupyter notebook appendix) ( 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.