Figure 1. A small snippet of the spreadsheet
Six months have passed since my last update, but I've finally worked through Chapter 2; thus concludes Volume 1. I was very serious about this reading project: almost every day, I would spend at least an hour working through exercises, eventually getting more than 80% done (meaning I solved it on my own or understood Knuth's solution). Needless to say, it was a greatly enlightening and enjoyable experience.
In Chapter 2, Knuth introduces the fundamental data structures of arrays, stacks, queues, deques and trees, then he discusses memory management methods such as garbage collection and dynamic allocation (malloc). The latter half was relevant back when the volume was written in 1968 — memory was scarce and there was no operating system to delegate the dirty work of managing memory.
Nowadays these topics are covered in other texts, but I am very fond of Knuth's treatment. Firstly, he is deeply involved with low-level implementation details — a reflection of that era in which programs were written in machine language. For example, he would give the sequence of MIX instructions for inserting a node into a linked list from a pool of available memory. Such discussion may seem outdated to a modern eye, but personally I greatly appreciated it.
I learned to see the computer as a giant canvas of memory in which we can structure data as we see fit to solve the problem at hand. Adopting this point of view makes programming a fun and empowering activity.
Quoting Knuth from Selected Papers on Design of Algorithms: "Something magically beautiful happens when a sequence of commands and decisions is able to marshal a collection of data into organized patterns or to discover hidden structure."
A data structure can be implemented in different ways. A queue can be represented as an array with front and rear pointers, but it also can be represented as a linked list (Program 2.2.3T). Or, there are multiple ways of storing a List node (2.3.5), with subtle differences when performing algorithms over the List. Being flexible with implementation details is a part of programming technique.
Secondly, each section is accompanied by a nontrivial program demonstrating the data structure. The most impressive one is surely his elevator simulation program, where a doubly linked circular queue stores the sequence of events to be processed as time progresses. These example programs are not only interesting in their own right, they also show how seemingly complex programs can be broken down into relatilvely simple principles of operation. I think this helped instil confidence in me to tackle larger projects — for instance I never imagined being able to write a malloc before.
Thirdly, the exercises are top-notch. Sometimes Knuth shares some super cool fact (did you know a binary tree can be traversed without using a stack?); sometimes he gives you an opportunity to hone your programming technique (write this program in MIX... and then analyse its runtime). I found his solutions are well worth reading even if I could solve them confidently: he might use a better method, or he might supply remarks providing insight/motivation/history, or he might go on a page-long tangent to solve a much more general version of the exercise. All in all, I cannot claim to have learned much from TAOCP if I did not work through the exercises meticulously.
So I've given my 3 big reasons for liking TAOCP. But I also want to give a shoutout to the mathematical sections because they have such interesting material:
2.3.4.1 for its direct relevance to program analysis;
2.3.4.2 for the method of constructing Eulerian trails;
2.3.4.3 for the mindblowing fact that a plane can be tiled with tetrads if its upper right quadrant can;
2.3.4.4 for the masterful manipulation of generating functions and the shocking correspondences.
I tracked my progress systematically using a spreadsheet. Every single exercise was given a row, and it would be marked NOT DONE or DONE. As more and more got marked DONE, I could clearly see the progress I was making, and this was an important source of motivation. Occasionally I would skip an exercise so that I would not get stuck at one place and burn out.
|
|
Figure 1. A small snippet of the spreadsheet |
Moving on, I plan to read Chapter 3 which is about random numbers. I expect progress to be slower because it is math-heavy and math exercises take longer to solve based on experience; furthermore I have more university commitments.