tcs
tcs copied to clipboard
boazbk
Book in preparation: introduction to theoretical computer science
In the 'Finding the shorest path in a graph' section (12.1.1) of chapter 10 (Efficient algorithms), we have that using a queue gives us an `O(m)` way of finding the...
Please open a different issue for each chapter, with the **chapter name** in the title - thank you! Please edit the fields below Chapter 13: Theorem 13.9 (Time Hierarchy) Proof...
Please open a different issue for each chapter, with the **chapter name** in the title - thank you! Please edit the fields below **Chapter 13, Modeling Running Time**: The names...
**Chapter name**: Polynomial-time reductions **List of bugs/typos** The reference to Figure 14.6 in this chapter in the vertex cover exercise appears in the PDF as "see ??" but is fine...
proof of theorem 11.3 (in section 11.2) is WRONG. A right proof as follows: Let ALL = all turing machines H = {M | M is a turing machine and...
In the computation and representation chapter, there is some confusing naming that could be improved. For instance in lemma 2.8  F is used to mean a set of functions...
On page 303, the \lambda y. gz should have a larger space between "g" and "z" to make clear that z is the argument to the function \lambda y.g (from...
Please open a different issue for each chapter, with the **chapter name** in the title - thank you! Please edit the fields below **Chapter name**: Equivalent Models of Computation, Turing...
**Chapter name**: What if P equals NP? **List of bugs/typos** 1. In the pink box sectioned, ***This chapter: a non mathy overview***: There should be a hyphen between "non" and...
