×

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.

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.