×

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 620 pages, 18MB). 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.

Lectures

Preface ( pdf version , MS word version: imperfect)

0. Introduction ( pdf version , MS word version: imperfect)

1. Mathematical background ( pdf version , MS word version: imperfect)

2. Representation ( pdf version , MS word version: imperfect)

3. Defining computation ( pdf version , MS word version: imperfect)

4. Syntactic sugar, and computing every function ( pdf version , MS word version: imperfect)

5. Code and data ( pdf version , MS word version: imperfect)

6. Programs with loops ( pdf version , MS word version: imperfect)

7. Other models ( pdf version , MS word version: imperfect)

8. Uncomputability ( pdf version , MS word version: imperfect)

9. Restricted computational models ( pdf version , MS word version: imperfect)

10. Gödel’s Incompleteness Theorem ( pdf version , MS word version: imperfect)

11. Efficient algorithms ( pdf version , MS word version: imperfect)

12. Formally defining running time ( pdf version , MS word version: imperfect)

13. Polynomial-time reductions ( pdf version , MS word version: imperfect)

14. NP, NP completeness, and the Cook-Levin Theorem ( pdf version , MS word version: imperfect)

15. What if P=NP? ( pdf version , MS word version: imperfect)

16. Space bounded computation ( pdf version , MS word version: imperfect)

17. Review of probability ( pdf version , MS word version: imperfect)

18. Randomized algorithms ( pdf version , MS word version: imperfect)

19. Modelling probabilistic computation ( pdf version , MS word version: imperfect)

20. Cryptography ( pdf version , MS word version: imperfect)

21. Proofs and algorithms ( pdf version , MS word version: imperfect)

22. Quantum computing ( pdf version , MS word version: imperfect)

A. The NAND programming language (Jupyter notebook appendix) ( pdf version , MS word version: imperfect)

B. The NAND++ programming language (Jupyter notebook appendix) ( pdf version , MS word version: imperfect)

C. Lambda calculus (Jupyter notebook appendix) ( pdf version , MS word version: imperfect)

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.