Book in preparation: introduction to theoretical computer science
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
.github/ISSUE_TEMPLATE Update issue templates May 31, 2018
.gitattributes fixed typos chapter 1 Aug 2, 2017
CONTRIBUTING.md make all auto commit Aug 8, 2017
LICENSE.md Create license file Jul 26, 2017
OLD_lec_03_computation.md Uniformize usage to "grade-school" Jul 1, 2018
OLD_lec_05_physical_implementation.md Use Big-$O$ Jul 1, 2018
README.md wip Jun 13, 2018
acknowledgements.md resolved conflict Sep 8, 2018
index.md make auto commit Jun 19, 2018
lec_00_0_preface.md resolved conflict Sep 8, 2018
lec_00_1_math_background.md fix some typos from open issues Sep 5, 2018
lec_01_introduction.md fix some typos from open issues Sep 5, 2018
lec_02_representation.md make auto commit Sep 13, 2018
lec_03_computation.md resolved conflict Sep 8, 2018
lec_03a_computing_every_function.md Uniformize usage to "grade-school" Jul 1, 2018
lec_04_code_and_data.md Reword all "equals to"s Jul 1, 2018
lec_05_physical_implementation.md Use Big-$O$ Jul 1, 2018
lec_06_loops.md make auto commit Sep 20, 2018
lec_06a_universality.md Uniformize usage to "grade-school" Jul 1, 2018
lec_07_other_models.md Fix expression of NAND using lambda calculus. Sep 12, 2018
lec_08_uncomputability.md Reword all "equals to"s Jul 1, 2018
lec_08a_restricted_models.md changed references to lectures to chapters Jun 18, 2018
lec_09_godel.md Merge pull request #175 from wfus/master Aug 6, 2018
lec_10_efficient_alg.md Reword all "equals to"s Jul 1, 2018
lec_11_running_time.md Merge branch 'master' into TCS-158/grade-school Jul 1, 2018
lec_12_NP.md changed references to lectures to chapters Jun 18, 2018
lec_13_Cook_Levin.md edits to quantum chapter Jun 24, 2018
lec_13a_advanced_reductions.md changed references to lectures to chapters Jun 18, 2018
lec_14_PvsNP.md edits to quantum chapter Jun 24, 2018
lec_14a_space_complexity.md changed references to lectures to chapters Jun 18, 2018
lec_15_probability.md make auto commit Jul 25, 2018
lec_16_randomized_alg.md changed references to lectures to chapters Jun 18, 2018
lec_17_model_rand.md [lec17] made some fixes to typos and unreferenced variables Jul 26, 2018
lec_18_hardness_vs_randomness.md changed references to lectures to chapters Jun 18, 2018
lec_18a_worst_case_derand.md changed references to lectures to chapters Jun 18, 2018
lec_19_cryptography.md changed references to lectures to chapters Jun 18, 2018
lec_20_alg_society.md changed references to lectures to chapters Jun 18, 2018
lec_21_compression_coding.md changed references to lectures to chapters Jun 18, 2018
lec_23_stream_automata.md changed references to lectures to chapters Jun 18, 2018
lec_24_proofs.md changed references to lectures to chapters Jun 18, 2018
lec_24a_interactive_proofs.md changed references to lectures to chapters Jun 18, 2018
lec_25_data_structures.md changed references to lectures to chapters Jun 18, 2018
lec_26_quantum_computing.md some remarks on quanutm chapter, background Jun 25, 2018
lec_26a_Shor_algorithm.md changed references to lectures to chapters Jun 18, 2018
lec_A_NAND_prog_lang.md wip Jun 2, 2018
lec_B_NANDpp_prog_lang.md wip Jun 7, 2018
lec_C_lambda.md wip Jun 2, 2018
macros.tex make auto commit Sep 13, 2018
metadata.yaml wip Jun 4, 2018

README.md

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 summer of 2018. My main priorities are:

  • Add explanations, proof ideas, examples.

  • Add exercises

  • Emphasize the "non importance" of the choice of particular models (NAND vs circuits, NAND++/NAND<< vs Turing machines/ RAM machines).

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

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.