5 ms·

Go ahead and get your free copy of Avi Wigderson's Mathematics and Computation https://www.math.ias.edu/avi/book https://www.math.ias.edu/avi/book. Broadly spe

Go ahead and get your free copy of Avi Wigderson's Mathematics and Computation https://www.math.ias.edu/avi/book https://www.math.ias.edu/avi/book. Broadly speaking there are two types of "CS Theory": 1. "What is computation and what can be computed?" That's what Wigderson's book is about. Complexity theory. 2. "What's the best way to compute something?" covered by "Introduction to Algorithms" and the like -- sth people ask on interview questions. In addition to the references here, http://people.cs.uchicago.edu/~laci/17discrete/ http://people.cs.uchicago.edu/~laci/17discrete/ gives some good puzzles to work through.

ykevinator 7y ago
Perfect answer, I second this.
- nextos 7y ago
  A related reference, cited by this book, and a bit shorter and simpler is Garey & Johnson Computers and Intractability. It's a really good classic little textbook.
deleted 7y ago
[deleted]
vicaya 7y ago
3. "What's the best way to specify computation?" covered by programming language and compiler books.
mlevental 7y ago
>Go ahead and get your free copy of Avi Wigderson's Mathematics and Computation https://www.math.ias.edu/avi/book https://www.math.ias.edu/avi/book. i've seen some ridiculous virtue signaling recommendations on hn before but this takes the cake. have you actually read the book? wigderson is an IAS professor (for those that don't know, einstein and godel were IAS professors) and this book is a research survey (most of the theorems have refs to papers). i've read both sipser and hopcroft ullman and i'm still pretty far away from being able to easily read it. and you're recommending this to someone that learned js from a bootcamp. you think maybe she's not the target audience? so that i'm not labeled as just a critic: the standard formal languages book is sipser https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X https://www.amazon.com/Introduction-Theory-Computation-Micha... it's colloquial and has a lot of diagrams and "intuition". people really like it but i actually think hopcruft ullman is better because it's more structured https://www.amazon.com/Introduction-Automata-Theory-Languages-Computation/dp/0321455363 https://www.amazon.com/Introduction-Automata-Theory-Language...
- crispinb 7y ago
  I can't speak to the parent's motivations, but having had a glance at this, it's clearly an entirely absurd suggestion. Section 1.4 outlines its intended audience. It (rightly) doesn't include programmers wanting to 'get started' in CS.
- charlescearl 7y ago
  Hey sorry, point taken. I have read chapters and was excited about it, but I see your point. Thanks for the suggestions. I found the book more readable than hopcroft ullman from the perspective of understanding what happens in "theoretical computer science" -- I encountered it decades after grappling with hopcroft ullman (so-called "Cinderella book".) I always find that the best books technically have been those that I take a bite from, think through an idea, maybe check out the references, find a problem to work through, then come back. Here's a quote from the intro that resonated: "Many parts of the book require hardly any specific prior knowledge and rely mostly on the mathematical maturity needed to take in the definitions and notions introduced. Hopefully, the story telling makes the reading even easier. However, the book (like the field itself) is conceptually dense, and in some parts the concentration of concepts and ideas requires, I believe, slowing down, rereading, and possibly looking at a relevant reference to clarify and solidify the material and its meaning in your mind." > wigderson is an IAS professor True, but I think he does a good job of explaining things. This lecture on incompleteness seemed accessible to me https://www.youtube.com/watch?v=0Zmfv3jsiQ0&t=1788s https://www.youtube.com/watch?v=0Zmfv3jsiQ0&t=1788s There's also Sanjeev Arora's book "Computational Complexity: A Modern Approach" https://theory.cs.princeton.edu/complexity/book.pdf https://theory.cs.princeton.edu/complexity/book.pdf

ykevinator 7y ago

Perfect answer, I second this.

nextos 7y ago
A related reference, cited by this book, and a bit shorter and simpler is Garey & Johnson Computers and Intractability. It's a really good classic little textbook.

deleted 7y ago

[deleted]

vicaya 7y ago

3. "What's the best way to specify computation?" covered by programming language and compiler books.

mlevental 7y ago

>Go ahead and get your free copy of Avi Wigderson's Mathematics and Computation https://www.math.ias.edu/avi/book https://www.math.ias.edu/avi/book. i've seen some ridiculous virtue signaling recommendations on hn before but this takes the cake. have you actually read the book? wigderson is an IAS professor (for those that don't know, einstein and godel were IAS professors) and this book is a research survey (most of the theorems have refs to papers). i've read both sipser and hopcroft ullman and i'm still pretty far away from being able to easily read it. and you're recommending this to someone that learned js from a bootcamp. you think maybe she's not the target audience? so that i'm not labeled as just a critic: the standard formal languages book is sipser https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X https://www.amazon.com/Introduction-Theory-Computation-Micha... it's colloquial and has a lot of diagrams and "intuition". people really like it but i actually think hopcruft ullman is better because it's more structured https://www.amazon.com/Introduction-Automata-Theory-Languages-Computation/dp/0321455363 https://www.amazon.com/Introduction-Automata-Theory-Language...

crispinb 7y ago
I can't speak to the parent's motivations, but having had a glance at this, it's clearly an entirely absurd suggestion. Section 1.4 outlines its intended audience. It (rightly) doesn't include programmers wanting to 'get started' in CS.
charlescearl 7y ago
Hey sorry, point taken. I have read chapters and was excited about it, but I see your point. Thanks for the suggestions. I found the book more readable than hopcroft ullman from the perspective of understanding what happens in "theoretical computer science" -- I encountered it decades after grappling with hopcroft ullman (so-called "Cinderella book".) I always find that the best books technically have been those that I take a bite from, think through an idea, maybe check out the references, find a problem to work through, then come back. Here's a quote from the intro that resonated: "Many parts of the book require hardly any specific prior knowledge and rely mostly on the mathematical maturity needed to take in the definitions and notions introduced. Hopefully, the story telling makes the reading even easier. However, the book (like the field itself) is conceptually dense, and in some parts the concentration of concepts and ideas requires, I believe, slowing down, rereading, and possibly looking at a relevant reference to clarify and solidify the material and its meaning in your mind." > wigderson is an IAS professor True, but I think he does a good job of explaining things. This lecture on incompleteness seemed accessible to me https://www.youtube.com/watch?v=0Zmfv3jsiQ0&t=1788s https://www.youtube.com/watch?v=0Zmfv3jsiQ0&t=1788s There's also Sanjeev Arora's book "Computational Complexity: A Modern Approach" https://theory.cs.princeton.edu/complexity/book.pdf https://theory.cs.princeton.edu/complexity/book.pdf