Week 37 of 125
TAOCP 2.2.4 and 2.2.5
Sign up or sign in to tick these off and give this week a due date.
-
Lists whose last node points back to the first, which makes some operations simpler. The main example is adding and multiplying polynomials stored as circular lists of terms.
Time About 5 hours this week
Why it matters
Circular lists are used in schedulers, LRU caches and buffer rings. The polynomial example is a great exercise in pointer surgery.
Before you start
- 2.2.3 Linked Allocation
How to approach it
Implement polynomial addition with circular linked lists in C, following the algorithm in the text. Test with polynomials that cancel terms.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Infinite loops when traversing a circular list without a sentinel or stop condition.
-
Lists with links in both directions, making deletion and insertion anywhere cheap. Knuth illustrates them with a detailed discrete-event simulation of an elevator system.
Time About 7 hours this week
Why it matters
Doubly linked lists underpin LRU caches and editor buffers, and the elevator simulation is a crash course in discrete-event simulation, a technique still used for modeling systems.
Before you start
- 2.2.4 Circular Lists
- 1.4.2 Coroutines
How to approach it
Implement a doubly linked list with a header node and test insert and delete at all positions. The elevator simulation is long: read it for structure, focus on how the event list works, and do not try to trace every MIX line.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Updating only one of the two links on insert or delete. Write the four pointer updates down before coding them.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.