Ask HN: Looking for a book on algorithms and data structures

Can you elaborate on "out of date"? I've seen a lot of books considered out of date because of their publishing date, but to what's exactly being compared to be considered so?

The annoying thing as you note is that in the long run Sedgewick >> Leetcode but in the short run it's probably reversed as whiteboard interviews often present algorithm puzzles that are variants of "have you seen this trick before?" and closer to Leetcode questions.

I wonder though if "programming contest" (usually more like "algorithm puzzle contest") books like Skiena's might be useful, though I can't help but think that doing an algorithms course first shouldn't be useless.

There are literally hundreds of threads with this topic on the Web. Most of them contain the same standard references which IMO are not always the best for people without much mathematical maturity and wishing to learn from first principles. That said, here are my recommendations for them (pdfs of almost all are available online and they can also be purchased cheaply as used books);

* 1) Functions and Graphs and 2) The Method of Coordinates by I.M.Gelfand et. al. - These give you the basics on functions and how to visualize them which is crucial for understanding.

* Introductory Logic and Sets for Computer Scientists by Nimal Nissanke - Nice succinct introduction to various required topics for Comp. Sci.

* Compared To What?: Introduction to the Analysis of Algorithms by Gregory Rawlins - This is a classic book which takes you by hand and walks you through Algorithm Analysis and the reqd. mathematics. You will find this more approachable than most other text books and well worth a study.

* How to Think about Algorithms by Jeff Edmonds - Practical techniques without too much mathematical formalism.

* Data Structure Techniques by Thomas Standish - A Classic text; good adjunct to more modern texts.

* Advanced Data Structures by Peter Brass - Nice succinct text but not necessarily "advanced".

One final point; try to get a Algorithms and Data Structures book with code in the language with which you are most familiar. That way you understand the mapping from "Abstract Algorithm" to "Concrete Language Implementation" which is not always trivial.

I came here precisely to suggest Skiena. Excellent book that gives you a good grounding in both theory and practice, and opens the road for further study, if you're so inclined.

Well, Volume 4 was released in 2016 and is not out of date at all. Its a very good read, but on an obscure subject.

But Volume 1 has lots of out-of-date advice and is somewhat of a shame, because its otherwise an excellent introduction to computing + the mathematics needed to understand computing. For example, the assembly language is based on the 1960s computers, such as decimal computing and 6-bit numbers (based on the days of old, before 8-bits were standardized).

Functions are introduced by self-modifying code first and foremost: by rewriting "jump" instructions at the end of functions as a return. No one does this anymore: pretty much all compilers do the stack-thing instead. (Push return address onto a stack register).

The Fascicle on MMIX updates a lot of those sections to a modern-like 64-bit assembly language. However, the sections on cofunctions, arrays, garbage collection aren't part of that update... and should be updated (Knuth's discussion on these concepts is great, but are told in an "old way" based on 1960s tech)

Volume2: Seminumerical Algorithms (chapter 3 / 4) is again, a decent introduction to the subject. But the RNG stuff is fully obsolete. The statistical tests may have passed muster in the 1970s or 1980s, but today's statistical tests (aka: PractRand) go above and beyond what Knuth discusses.

There's a lot of interesting discussions in the randomness chapters: such as the efficacy of multiplication when it comes to bit-mixing (and I feel like modern RNGs are sleeping on that tidbit), but modern RNGs are generally based on a simpler sequence of ADD / XOR / SHIFT instructions based around the concept of permutations / perfect bijections.

----------------

Ironically, I consider the section on "tape sorting" to be "suddenly up-to-date" again. Modern RAM acts more like a tape (sequential is far faster than random), meaning that thinking of sorting problems in terms of external-sort is surprisingly relevant.

Given that today's cache is 768MB (see AMD's Milan-X CPUs: expected to be a ~$5000 CPU-server chip), we see that L3 cache basically serves as the RAM from Knuth's time, while today's DDR4 RAM really acts as the fast-sequential / slow-random layer that Knuth studied so much.