Hacker News new | past | comments | ask | show | jobs | submit login
Ask HN: What book to read to get a footing in CS theory?
306 points by bjackman on Aug 18, 2019 | hide | past | favorite | 82 comments
A friend of mine has just taught herself the basics of JavaScript then done a code boot camp. She's pretty comfortable writing code now, but hasn't had a chance to get to grips with stuff like complexity analysis yet.

It seems to me like she's a member of a large and growing target audience for a book that gets you started with all the stuff you would learn in a computer science degree, with the assumption that you already know how to express an algorithm as code.

Can anyone recommend such a book?




Jeff Erickson's Algorithms text is a great resource: http://jeffe.cs.illinois.edu/teaching/algorithms/

The entire book -- including the portions labeled Models of Computation, Director's cut, and Extended Dance Remix -- presents accessible introduction to much of the CS theory landscape.

Someone already praised the shorter book titled "Algorithms" by Dasgupta et al, and I second it. Tim Roughgarden's "Algorithms Illuminated" series is in this genre too.

I'd also recommend the MIT lecture notes on Mathematics for CS: https://courses.csail.mit.edu/6.042/spring18/mcs.pdf This is distinctive for its intuitive explanations with essential, approachable formalism. The exercises are fine too, if you are really mean it.

Sipser's book on the Theory of Computation is great and the one by Hopcroft et al is also very good (as suggested by others). But the most beginner-friendly (or, light on math) coverage of this area is apparently in Peter Linz's book "Introduction to Formal Languages and Automata". An alternative flavor in the treatment of much of the same topics is in this free book: http://cs.brown.edu/people/jsavage/book/


Trivia: Jeff's book's cover says Al-Khwarizmi [0] in geometric Kufic [1] script: He was a scholar in Baghdad's House of Wisdom after whom the word Algorithms takes root. Al-Khwarizmi also introduced al-Jabr (algebra) and the Indian decimal system to the west.

His contemporaries in Basra, Iraq united Greek (Hellenistic, Hermetic, Neoplatonic, Pythagorean, Ptolmic), Indian, Judeo-Christian scientific, religious, astronomical, cosmological, and philosophical works [2].

Later, Bukhara and Cairo would go on to rival Baghdad until the demise of Islamic Golden Age at the hands of Hulagu Khan.

[0] https://en.wikipedia.org/wiki/Muhammad_ibn_Musa_al-Khwarizmi

[1] https://en.wikipedia.org/wiki/Kufic

[2] https://en.wikipedia.org/wiki/Encyclopedia_of_the_Brethren_o...


+1 for Dasgupta (DPV). It is used at GT and Berkeley in CS.

http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-...


Any solution manual?


Go ahead and get your free copy of Avi Wigderson's Mathematics and Computation 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/ gives some good puzzles to work through.


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


Perfect answer, I second this.


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.


[flagged]


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

There's also Sanjeev Arora's book "Computational Complexity: A Modern Approach" https://theory.cs.princeton.edu/complexity/book.pdf


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.


For CS theory, I would rather suggest you to focus on classic CS courses, here's my list:

0. Do not touch "Introduction to Algorithms" until you are in a dream job.

1. CS 61A: The Structure and Interpretation of Computer Programs https://cs61a.org/

2. CS61B: Data Structures http://datastructur.es/sp16/

3. Coursera: Princeton Algorithm https://coursera.org/learn/algorithms-part1

4. CMU 15213 CSAPP https://courses.cs.washington.edu/courses/cse351/16sp/videos...

5. Keep moving.


Is the Stanford Algorithms course a good or equal substitute? I started the Princeton one, but the homework was... just not what I would have expected or often threw me for a loop.


Princeton one is not job interview focused, but is good for one to get started in this field.


> Do not touch "Introduction to Algorithms" until you are in a dream job

Any idea why? Its unlikely I'll ever land my "dream job" butnim curious as to the reasoning.


If by "Introduction to Algorithms" we mean the infamous book by Cormen et al...

When I propose to use it to prevent sea rise by drying the sea I only half jest. It's IMO one of the worst books to use except as reference when you already have a good grounding.


It's an awesome book but kinda theoretical, I'd suggest to read and digest it slowly after you got a great job, not before.


Why not "Introduction to Algorithms"?


ditto, it's an awesome book but kinda theoretical, I'd suggest to read and digest it slowly after you got a great job, not before.


https://teachyourselfcs.com/


Well this is superb. I've traditionally given my own piecemeal answer to the teach-myself-cs question, but I'll be handing this link out in future.


Just want to highlight this with an additional comment - as someone who went through a CS degree and was heavily interested in CS pedagogy and compared many a CS curriculum, this is a great compilation of great resources.


Skiena's Algorithm Design Manual:

https://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena...

Far more readable than the usual text (Cormen), the first half is a guide on how to select and design algorithms for the problems you encounter, and the second half is a whistle-stop tour of hundreds of well-known algorithms. The tour helped me a lot with X->Y esque issues where I was building bad solutions because I didn't know anything better could exist.

Incidentally, there's a lot more to CS theory than algorithms and data structures, but if you're asking on HN for a generic CS theory book, I reckon it's most likely an algorithms and data structures book that you're after.


I'm going to disagree slightly with your choice (which was also my choice at first). While A.D.M. has all the topics you would be interested in, I think the book assumes that you have already groked the fundamentals behind, say, why a linked list is different from an array. For an absolute beginner, I would suggest the type of book that forces you to go through every step of deleting an item from a list, which is something Skiena's book (luckily) doesn't do. The book is great for learning new ways to think about problems, but IMHO a beginner should learn the basic ways first.

"Introduction to Algorithms" by CLRS seems to be the default choice, and it seems to me to be a step in the right direction (based on the TOC).

I would also like to second your point that CS is more than algorithms and data structures. I feel Dijkstra would not approve of thinking about CS as "that thing you do after learning a programming language".


I found "Introduction to Algorithms" to be _waaay_ too dry to deal with in beginning, though I'd welcome something else to get through the detail.

Personally I'd use Cormen as "dictionary" to get into detail of stuff I first read in A.D.M.


This is really helpful, thanks. It's been... a few years since I read Skiena, and I came to it from a maths background. I'll add the disclaimer in future that Cormen's easier to start with.


I wrote two of them specifically for self taught programmers like her: “Classic Computer Science Problems in Python” and “Classic Computer Science Problems in Swift.” Unfortunately we don’t have a JavaScript version yet. Instead of focusing on things like complexity analysis we focus on problem solving techniques in a tutorial like fashion. You can find out more at: https://classicproblems.com


Not OP but will check those out, thanks!


Why python and not a proper oop language tho?


There's so much more to CS theory than big O notation and you're in for a treat if you check out any of the below - happy to share more if people are interested.

1. https://www.amazon.com/Computational-Complexity-Approach-San...

2. https://www.amazon.com/Quantum-Computing-since-Democritus-Aa...

3. https://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden...

4. https://www.amazon.com/Introduction-Theory-Computation-Micha...


Before deep diving into CS theory, I would go deeper into programming first to better understand how a computer really works. The best intro on this topic I found is "Programming from the Ground Up" by Jonathan Bartlett [1].

"Programming from the Ground Up" starts at the bottom with CPU architecture and goes up from there to how functions work, dealing with files, code libraries, high-level languages, etc. Having a solid understanding here will provide immediate benefits in coding and serve as a strong foundation for some of the other recommended texts.

If you're interested, I recommend buying directly from Bartlett Publishing [1]. Bartlett published the book under the GNU Free Documentation License and there are multiple copy-cat versions on Amazon.

[1] http://www.bartlettpublishing.com/site/catalog/programming-f...


Would like to add Nand2Tetris[1] which falls in a similar category.

[1]: https://www.nand2tetris.org/


I actually recommended this to her already - the book (The Elements of Computing Systems) of the same course was the first programming text I ever read. Really enthralling!


Structure and interpretation of computer programs (free online) https://en.wikipedia.org/wiki/Structure_and_Interpretation_o...


Aho/Ullman Foundations of CS http://infolab.stanford.edu/~ullman/focs.html

O'Halloran/Bryant CSPP https://csapp.cs.cmu.edu/

David Money Harris Digital Design... https://booksite.elsevier.com/9780128000564/


Comprehensive and Worthy suggestions.

The first one was new to me. Looks quite good.


The classic "Foundations of CS" was referred to in my youth as simply "Aho and Ullmann". As I recall, it contained a particularly comprehensive explanation of the construction of parsers, compilers, interpreters and translators.


You are thinking of a different book by "Aho and Ullman". The text listed above deals more with "Discrete Maths" and "Computer Science".


Most of these answers seem to be books about algorithms.

Computer science is much broader than that; it includes databases, AI (not the same as algorithms!), computer architecture, topics such as hardware interfacing, history of computing, and some overlap with areas in philosophy.

I didn't ever formally study CS, but I did read several books on algorithms. Especially notable is the seven-volume work "The Art of Computer Programming" by Donald Knuth; in particular the volumes "Fundamental Algorithms", "Sorting and Searching", and "Seminumerical Algorithms" are timeless masterpieces, entertaining and witty, and they totally nail their subject-matter. If you think CS is equivalent to "algorithms", then read these books.

N.B. I understand that some of these books have been re-written to use a revised version of Knuth's MIX machine language, to allow the examples to embody modern developments such as pipelines, caches, and parallelism. I haven't read these updated editions; no doubt they are even better than the originals.

But I think CS is a much broader field than algorithms.

[edit] Harrumph. Wikipedia says that only three-and-a-bit volumes have yet been published. Seven volumes was the original plan. Smacks a little of George R. R. Martin?


> Harrumph. Wikipedia says that only three-and-a-bit volumes have yet been published. Seven volumes was the original plan. Smacks a little of George R. R. Martin?

My favourite poke at this is Charlie Stross' book the Atrocity Archives (a kind of Lovecraftian, CS nerd horror / humour novel where advanced mathematics is dangerous), wherein Knuth did in fact finish the 4th edition, but it contained secrets that immediately got it shut down by various governments.


> have been re-written

There’s a plan in place to do so, but as of now, the current editions of the first three books are still written using MIX (the 60’s-style assembler language that he invented for the original editions). The later volumes do use the more modern MMIX.


What!!!

Is this some sort of a joke? Do not troll here.


See what some (reputable) universities in your country use for their data structures and algorithms class, and then use that.

Avoid books with a programming language in the title, because those will try to teach both basic programming and the interesting material.


I strongly advise the following:

- The Computational Beauty Of Nature, by William Gary Flake

- The Impostor’s Handbook, by Rob Conery

- The Elements Of Computing Systems, by Noam Nisan & Shimon Schocken


I’m a fan of Algorithm Design Manual. It’s also what Google and FB recommend for interview prep.

https://smile.amazon.com/Algorithm-Design-Manual-Steven-Skie...


For a gentle introduction to algorithms and Big O, "Grokking Algorithms" is easy to read and fun. For more in depth and systematic study, Sedgwick's "Algorithms" is a very clear and beautiful book.

For computer architecture, Petzold's "Code" is wonderful.


Mike Sipser's book: https://www.amazon.com/dp/113318779X


This is a great book. I recommend learning this book with professor Porter's course on theory of computation. https://www.youtube.com/watch?v=TOsMcgIK95k&list=PLbtzT1TYeo...


The New Turing Omnibus: Sixty-Six Excursions in Computer Science https://www.amazon.com/dp/0805071660


Probably a little more advanced than what you are looking for but I would like to recommend The Nature of Computation by Cristopher Moore and Stephan Mertens as a next step. It is such a fun book to read, with a lot of problems and exercises.

http://nature-of-computation.org/


You mentioned getting to grips with complexity analysis. Has she looked at the book Think Complexity[1]? It seems pretty cool and related to that area of study.

[1]: http://greenteapress.com/complexity/


Mentioned before, but I'll +1 these: - The Impostor’s Handbook: Rob Conery - Foundations of CS: http://blough.ece.gatech.edu/3020/focs.pdf

Also be sure to check out

- Software Fundamentals, essays by David Parnas

Here's one of the essays from the book: https://www.win.tue.nl/~wstomv/edu/2ip30/references/criteria...

Parnas promoted the idea of encapsulation before the word had even been invented. And at the time, the idea was actually controversial, if you can believe it.


I'm a CS grad student at Caltech. My absolute favorite intro theory book (the one I recommend to undergrads and people just starting out) is Algorithms by Vazirani, Dasgupta, and Papadimitriou. Extremely well written and a great selection of topics.


I would recommend the Dasgupta and Vazirani book on algorithms. It has a balance between theory and practice. Plus it has a lots and lots of exercises which I found very helpful for practising.


I already addressed your question in another comment, but I would like to write a second point: a book seems to me the wrong way to go.

Unless your friend is a natural born comp. scientist, she'll need someone to point out what's important, what's not, which exercises she must solve before moving on and which topics she can take in parallel if she needs a break.

Of course, a course takes time. But if someone doesn't find the time to take an online course, where will they find the time to (properly) read the book?


I suppose a book could be written more as a course than a comprehensive reference manual?


A really good overview of the field of CS is _Great Principles of Computing_ by Peter Denning and Craig Martell, 2015. It's a good book for CS students who want overviews of less familiar areas of computer science, and for anyone (in other areas) who want to know more about computation.

Another is Subrata Dasgupta's _Computer Science: A Very Short Introduction_, a 2016 addition to Oxford's Very Short Introduction series. It has over five pages of further references to more detailed and specialized works.


Penn has a master's program, the MCIT (https://onlinelearning.seas.upenn.edu/mcit/), that's designed to be a highly condensed undergraduate program in computer science. The materials from the core courses there are a very good place to start looking. My guess is that the bootcamp covered mostly stuff from 591 and 594, so the other four courses will be new.


You should start reading The Art of Computer Programming by Donald Knuth, and solve all exercises (including ones having difficulty level 50). If you catch up finishing all currently existing volumes before Knuth finishes, with all the exercises answered thoroughly; you can consider yourself a self-taught algorithms expert.


PAPL https://papl.cs.brown.edu/2018/index.html There's lectures for it too: https://brown.hosted.panopto.com/Panopto/Pages/Sessions/List...

Tell your friend to download the lectures locally before they disappear. It will cover estimating complexity, solving recurrences, memoization, dynamic programming, etc. All the assignments can be done in a browser as they're in Pyret.

Ripping the vids cannot be emphasized enough, these lectures always disappear after a few months.


For understanding complexity watch this video https://www.infoq.com/presentations/Simple-Made-Easy/

Another way to thing theory of programming logic is a general understanding of language logic for which I recommend https://www.amazon.com/Philosophy-Language-P-Martinich/dp/01...

I am going through that book myself right now. It came to me highly recommended. I don’t have a computer science degree.


Bentley, "Programming Pearls"

https://www.goodreads.com/book/show/52084.Programming_Pearls


"complexity analysis" ... "stuff you would learn in a computer science degree".

Does she want theory? Does she want Software Engineering skills? Does she want to be able to get a job?

Cracking the Code Interview might be a fine jumping off point. It covers a lot of topics at a very readable level. If she doesn't understand it from the books angle, then she can do research on her own until she gets there. It covers stuff like "complexity analysis" in-depth enough for most people.


I would highly recommend Imposter's Handbook[1] by Rob Conery

Then there is also excellent BaseCS Podcast [2]

[1] https://bigmachine.io/products/the-imposters-handbook [2] https://www.codenewbie.org/basecs


I would find it very difficult to recommend this book - I think parts of it are simply factually mistaken, unfortunately, and I worry someone using knowledge from it would make themselves look like more of an imposter, not less.

https://github.com/imposters-handbook/feedback/issues/50

The book itself is a good idea and the author seems to have good intentions even if they didn't take advice in this case, though.


'The CS Detective' is the most well written introduction to Computer Science theories I have ever come across: https://nostarch.com/csdetective

It is approachable, fun, and engaging. It frames concepts inside a 'detective' story, making the explanations less abstract and more practical.


Structure and Implementation of Computer Programs. A master piece, a bit challenging but immensely fun for a certain kind of people.


Also "The Elements of Computing Systems", which is as good as SICP but comes at CS from opposite direction, that is from the machine up.


Typo for "Structure and Interpretation of Computer Programs"?


Yes, thank you.


Algorithmics by David Harel. Not a textbook, but a more popular Scientific American level treatment. Very readable and accessible but quite rigorous also - Harel's a noted computer scientist. I recall there was a slightly different edition of this book called something like Algorithms - the Soul of Computing.


Seconded. This is a good recommendation particularly for somebody who is just starting out (the OP has only done a js bootcamp and so has a very long way to go!)

Pair the above with Petzold's "Code" and you get a very good idea of both the Theory and the Machine.


I second the suggestion "Foundation of Computer Science" the full book is available as pdf. its language is clear. it uses C langauge. there is another edition using Pascal (which I have and IMHO is better even when learning about data structures involving memory references). you may also find a dirt cheap used copy.


Are there any recommendations for books thats are less algorithms and more how to structure software, how to structure databases and data and how to build reliable apps/websites and reduce spaghetti code?


At the Architecture level see the very good book "Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems" by Martin Kleppmann.

For actual code, you do not have one book but have to glean the knowledge from a whole bunch of them.


There is a book called Grokking Algorithms (forgot the author), it's a more gentle intro to algorithnd, I would strongly advise that book for someone that completed a bootcamp.


It's not just algorithms. Creating maintainable code and building good habits matter too.

For that, I'd recommend The Pragmatic Programmer, A.Hunt, D.Thomas.


Maybe it would be possible to give a somewhat useful first answer just as a post here; I'll try.

Going way back in computing, often an important issue was, how fast will a program run? That study is now sometimes called computational time complexity.

This study was important because, for some common work, some ways of programming the work ran many times faster than some other ways -- i.e., the study of computational time complexity got some big results.

Usually in practice an issue of a little less concern than running time was how much of the computer main memory would a program need, and this study was computational space complexity.

The first big case of big gains was running time for sorting. So, for some positive integer n, we are given n numbers (or alphabetic names, etc.) and want to sort them into ascending order. So, an obvious first approach is to look at all n numbers one at a time and find the smallest. Then look at the remaining n - 1 numbers and again find the smallest. Then with a little algebra, the running time grows proportional to n^2 (n times n, n squared). So we say (I'm omitting some fine points) that the running time is "big O n^2" written

O(n^2).

Now for some big stuff: (1) There is a way (method, technique, algorithm) called heap sort with running time (computational time complexity)

O(n log(n) )

both on average for random numbers and also for the worst case of the order of the given n numbers. (2) Heap sort works by comparing numbers two at a time (so did our

O(n^2)

algorithm above), and there is a cute counting result from A. Gleason, long a math prof at Harvard, that shows that for sorting by comparing numbers two at a time

O(n log(n) )

is the fastest possible. (3) Heap sort is also in-place which means that the storage used, except for a constant independent of n, is just what is needed for the n numbers being sorted.

After sorting, there was interest in working with trees. Likely the tree most people are most familiar with is the hierarchical file system. A tree can be good for keeping a set of numbers in order while adding numbers to the set or removing numbers from the set. To get good guaranteed fast running time, we want the tree balanced, that is, all the paths in the tree from the root to the leaves are about the same length. So, keeping the tree balanced while making the changes and doing so with relatively fast worst case running time was a challenge. One solution was AVL trees (see D. Knuth's The Art of Computer Programming: Sorting and Searching or more recent books listed in this thread) and, mostly for data stored on disk, B-trees. Actually there are several important, that is, relatively fast, algorithms for manipulating trees.

Early on in computing there were more problems with algorithms that improved running time, e.g., string searching.

There is a general technique, dynamic programming, that is the basis of several important, relatively fast algorithms. Here the programming is in the sense of the English project planning, that is, from the field of optimization in operations research.

Generally, given a program, it can be difficult to do algebraic manipulations, say, assuming either random or worst case inputs, to find the "Big O" running time. Knuth's book starts with a lot of algebraic techniques that can help finding Big O running times. That work can be as challenging as we please.

There is some work that early on was not really in computer science but very much needs computers and where running time was and is a huge issue. An important source of such work was optimization in operations research. The first work of concern was the simplex algorithm of linear programming. Next was the closely related integer linear programming, i.e., combinatorial optimization. There were too many cases of problems starting with n numbers and running in

O(2^n)

which is exponential and so bad that, for too many realistic problems, we could run for billions of years with about the fastest computers we can imagine and big enough to fill the visible universe, literally.

So, a question became, can we have some positive integer k and have worst case running time grow only as

O(n^k)

that is, a polynomial in k? The problem was generalized and now is the question of P versus NP, the leading question in computational complexity and maybe in much of computer science and pure and applied mathematics. The standard example of such a problem is the traveling salesman problem were we are given some n cities and ask for the shortest path that visits each city exactly once.

That's a nutshell start on computational time complexity in computer science.


Errata: Should revise

"there is a cute counting result from A. Gleason, long a math prof at Harvard, that shows that for sorting by comparing numbers two at a time

O(n log(n) )

is the fastest possible."

by adding at the end "for worst case performance".

Should revise

"Then look at the remaining n - 1 numbers and again find the smallest."

by adding at the end "etc.".

Generally computer science computational complexity ignores long lists of ways to write code that runs faster, e.g., for a result needed more than once, compute it just once and store the result and don't repeat the calculation.

Instead, the emphasis is on some larger aspects, e.g., just counting comparisons. Broadly that emphasis is usually appropriate since as n grows quite soon some crude code of a O( n log(n) ) algorithm will run many times faster than careful code of an O( n^2 ) algorithm.


Errata: adding at the end "for average case performance".


Errata: O(n^k) is a polynomial in n.


"Most of the code you write is run by an operating system, so you should know how those interact."

All of the code you write is run by one or more CPUs; operating systems provide supporting software, they don't "run" programs (although they may schedule them for execution, which isn't the same).

</pedant-mode>


It’s not that clear cut. Virtual Memory for example is not just hardware.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: