richardxdh/tcs

Book in preparation: introduction to theoretical computer science

Introduction to Theoretical Computer Science

This is the git repository for a book in preparation for an introductory undergraduate course on computer science. The book is posted (in both html and pdf formats) on the web page http://introtcs.org

Please use the issues and pull requests to post any suggestions, comments, typo fixes, etc..

I am working on improving this text during the spring of 2019.

My priorities are:

• Make the book less "idiosyncratic" - emphasize the models of Boolean Circuits, Turing Machines and RAM machines as opposed to their programming-language variants. As a byproduct I am renaming the programming languages to NAND-CIRC, NAND-TM and NAND-RAM to emphasize their roots and connections to standard models.

• Add exercises

• More explanations, proof ideas, revisions.

• Write two chapters: space bounded computation and proofs and programs.

• Adding supplemental code, which will eventually be on github.com/boazbk/tcscode

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/ or send a letter to Creative Commons, PO Box 1866, Mountain View, CA 94042, USA.

While this text will remain freely and publicly available, I may also create a printed book version in the future. By making any contribution to this work, such as a typo fix or any other suggestion or edit, you are assigning me the rights to use your contribution in both the online or any other version of this work.