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.

For the best-formatted version, download all lecture notes in a single PDF file (about 300 pages, 3MB).

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 The class NP (pdf version)

16 The Cook Levin Theorem (pdf version)

17 More NP hardness reductions (advanced lecture) (pdf version)

18 What if P=NP? (pdf version)

19 Review of probability (pdf version)

20 Randomized algorithms (pdf version)

21 Modelling probabilistic computation (pdf version)

22 Hardness vs. randomness (pdf version)

23 Derandomization from worst-case assumptions (advanced lecture) (pdf version)

24 Cryptography (pdf version)

25 Algorithms and society (pdf version)

26 Compression, coding, and information (pdf version)

27 Space bounded computation (pdf version)

28 Streaming, sketching, and automata (pdf version)

29 Proofs and algorithms (pdf version)

30 Interactive and probabilistically-checkable proofs (advanced lecture) (pdf version)

31 Limits of data structures (pdf version)

32 Quantum computing (pdf version)

33 Shor’s algorithm (advanced lecture) (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.