Introduction to Theoretical Computer Science A free open textbook covering the foundational theory of computer science, used as a course material in Harvard’s undergraduate and graduate programs. What you’ll learn: basic mathematics, computational models, algorithms, computability, complexity theory, cryptography, randomized algorithms, quantum computing.

Introduction to Theoretical Computer Science: index

Source: https://introtcs.org/public/ 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 forHarvard CS 121. It is also used forUVa CS 3102andUCLA CS181.

See below for individual chapters. You can also download thebook in a single PDF file(about 600 pages, 10MB).

If you have anycomments, suggestions, typo fixes, etc.. I would be very grateful if you post them as anissueorpull requestin theGitHub repository boazbk/tcswhere I am maintaining the source files for these notes. You can also post comments on each chapter in the links below.

See thegithub.com/boazbk/tcscodefor jupyter notebooks with supplementary code for the book.

For prior versions of the book, see therepository release page. The most updated version of this book is always on this page.

**Frozen version for Fall 20223:**I will be only making minor edits (typos, local fixes) during the fall so as not to disrupt teaching. For consistency in references and exercises, instructors can use the following version frozen as of July 24, 2023:Introduction to TCS version 0.95

Book chapters

• **Chapter p:**Preface(PDF: best formatting,Word: buggy)
• **Chapter 0:**Introduction(PDF: best formatting,Word: buggy)
• **Chapter 1:**Mathematical Background(PDF: best formatting,Word: buggy)
• **Chapter 2:**Computation and Representation(PDF: best formatting,Word: buggy)
• **Chapter 3:**Defining computation(PDF: best formatting,Word: buggy)
• **Chapter 4:**Syntactic sugar, and computing every function(PDF: best formatting,Word: buggy)
• **Chapter 5:**Code as data, data as code(PDF: best formatting,Word: buggy)
• **Chapter 6:**Functions with Infinite domains, Automata, and Regular expressions(PDF: best formatting,Word: buggy)
• **Chapter 7:**Loops and infinity(PDF: best formatting,Word: buggy)
• **Chapter 8:**Equivalent models of computation(PDF: best formatting,Word: buggy)
• **Chapter 9:**Universality and uncomputability(PDF: best formatting,Word: buggy)
• **Chapter 10:**Restricted computational models(PDF: best formatting,Word: buggy)
• **Chapter 11:**Is every theorem provable?(PDF: best formatting,Word: buggy)
• **Chapter 12:**Efficient computation: An informal introduction(PDF: best formatting,Word: buggy)
• **Chapter 13:**Modeling running time(PDF: best formatting,Word: buggy)
• **Chapter 14:**Polynomial-time reductions(PDF: best formatting,Word: buggy)
• **Chapter 15:**NP, NP completeness, and the Cook-Levin Theorem(PDF: best formatting,Word: buggy)
• **Chapter 16:**What if P equals NP?(PDF: best formatting,Word: buggy)
• **Chapter 17:**Space bounded computation(PDF: best formatting,Word: buggy)
• **Chapter 18:**Probability Theory 101(PDF: best formatting,Word: buggy)
• **Chapter 19:**Probabilistic computation(PDF: best formatting,Word: buggy)
• **Chapter 20:**Modeling randomized computation(PDF: best formatting,Word: buggy)
• **Chapter 21:**Cryptography(PDF: best formatting,Word: buggy)
• **Chapter 22:**Proofs and algorithms(PDF: best formatting,Word: buggy)
• **Chapter 23:**Quantum computing(PDF: best formatting,Word: buggy)

Compiled on 12/06/2023 00:07:51

Copyright 2023, Boaz Barak. This work is licensed under aCreative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Produced usingpandocandpanflutewith templates derived fromgitbookandbookdown.