Week 43 of 125
TAOCP 2.3.4 Basic Mathematical Properties of Trees (part 2)
Sign up or sign in to tick these off and give this week a due date.
-
Part 2 covers counting trees (how many binary trees or labeled trees of each size exist), path length and its role in measuring tree cost, Huffman's method for building optimal weighted trees, and the section's history.
Time About 8 hours this week
Why it matters
Counting trees gives you Catalan numbers, which pop up everywhere. Huffman coding is used inside gzip, PNG and JPEG.
Before you start
- 2.3.4 part 1
- 1.2.9 Generating Functions
How to approach it
Derive the count of binary trees with n nodes using a generating function before reading Knuth's derivation. Implement Huffman coding with a priority queue and compress a text file.
Exercises
Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.
Traps
- Confusing internal and external path length. Write out both for a small tree.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.