Week 38 of 125
TAOCP 2.2.6 Arrays and Orthogonal Lists
Sign up or sign in to tick these off and give this week a due date.
-
Storing multidimensional arrays in memory, including triangular arrays, then sparse matrices stored as lists linked across both rows and columns, with a pivot step from matrix computation as the example.
Time About 7 hours this week
Why it matters
Row-major versus column-major layout decides cache behavior in numeric code. Sparse matrix storage is how graph algorithms and scientific computing handle huge, mostly empty data.
Before you start
- 2.2.5 Doubly Linked Lists
- Basic matrices
How to approach it
Derive the address formula for row-major storage yourself. Then implement the orthogonal list representation for a tiny sparse matrix and check it by printing rows and columns.
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
- Index arithmetic errors with triangular arrays. Test on a 4x4 case.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.