Week 56 of 125
TAOCP 3.5 and 3.6
Sign up or sign in to tick these off and give this week a due date.
-
A philosophical and mathematical attempt to define randomness for infinite and finite sequences, building up through stronger and stronger definitions and touching on what later became algorithmic (Kolmogorov) complexity.
Time About 6 hours this week
Why it matters
Mostly for intellectual depth, but it sharpens your intuition about why "passes some tests" can never fully define random, and connects to compression and cryptography.
Before you start
- 3.3 Statistical Tests
How to approach it
Read for ideas. Follow the sequence of definitions and why each one is too weak. The heavy proofs can be skimmed on a first pass.
Exercises
The exercises here lean heavily on M and HM ratings. Try a couple of the lower ones; skip the rest without guilt.
Traps
- Expecting a practical takeaway on every page. This one is about understanding.
-
Knuth Knuth 3.6 Summary
Knuth's practical summary of chapter 3: concrete advice on what kind of generator to use, how to use it, and what to avoid.
Time About 2 hours this week
Why it matters
The most directly practical few pages in the chapter.
Before you start
- Chapter 3
How to approach it
Read it and compare with what your language's standard library uses. Write down which generator your main language uses and whether it would pass Knuth's advice.
Exercises
This is a light section. Skim the exercises, do the ones rated 10 or under in your head, and spend the spare time catching up on earlier exercises you skipped.
Traps
- Using this advice for cryptography. Crypto needs a CSPRNG, a different problem.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.