[dragontamer]

Most algorithm books don't cover the math like summations or generating functions.

Chapter one of TAOCP for better or worse, is a very rigorous mathematics introduction.

I'm not recommending it for it's algorithms (which are unfortunately somewhat out of date). I'm recommending it because it's an incredible mathematics introduction, albeit a very difficult one.

[56V9qtdGKWy4q8p]

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?

[dragontamer]

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.

[exdsq]

The obvious example for me is the chapter on tape merging

[dragontamer]

Modern "RAM" is far faster at sequential than it is at random access.

So tape merging is in fact, useful again strangely enough. That's one of the sections that suddenly and surprisingly has regained relevance.