Sec. 1.2: Mathematical Preliminaries

This is the big section with the mathematical background required for algorithm analysis. The first time I started reading vol. 1, I spent a long time in this section, eventually losing interest. Not that I don’t like math, quite the contrary; but I started reading the book expecting algorithms, and it took too damn long to get to them. So here is what Knuth says in the beginning of this section:

The reader may choose to read the following subsections carefully, with implicit faith in the author’s assertion that the topics treated here are indeed very relevant; but it is probably preferable, for motivation, to skim over this section lightly at first, and (after seeing numerous applications of the techniques in future chapters) return to it later for more intensive study. If too much time is spent studying this material when first reading the book, a person might never get on to the computer programming topics!

And so it is that I am skimming this section. Later I can get back to it for some fun and games. I might also get back to read the whole Concrete Mathematics book, another one I started and never finished. Additional motivation to read the CMath book is that there is a free ebook called Concrete Math Companion, which presents J programs and algorithms related to subjects treated in CMath. Just imagine the geekiness factor of this whole endeavor. It boggles the mind.