Introduction to Theoretical Computer Science

Boaz Barak

Work in progress

These are lecture notes for an introductory undergraduate course on theoretical computer science. I am using these notes for Harvard CS 121.

You can also download all lecture notes 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.


0 Preface (pdf version)

0.5 Mathematical background (pdf version)

1 Introduction (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 Physical implementations (pdf version)

7 Programs with loops (pdf version)

7 Universality and indirection (pdf version)

9 Other models (pdf version)

10 Uncomputability (pdf version)

11 Restricted computational models (pdf version)

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

13 Efficient algorithms (pdf version)

14 Formally defining running time (pdf version)

15 Polynomial-time reductions (pdf version)

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

17 What if P=NP? (pdf version)

18 Review of probability (pdf version)

19 Randomized algorithms (pdf version)

20 Modelling probabilistic computation (pdf version)

21 Cryptography (pdf version)

22 Proofs and algorithms (pdf version)

23 Quantum computing (pdf version)

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

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