12 November 2019

TAOCP: Volume 4B, Fascicle 5

The Art of Computer Programming, Volume 4B, Fascicle 5: Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links

This fascicle covers three separate topics:
  1.  Mathematical Preliminaries. Knuth writes that this portion of fascicle 5 "extends the ‘Mathematical Preliminaries’ of Section 1.2 in Volume 1 to things that I didn't know about in the 1960s. Most of this new material deals with probabilities and expectations of random events; there's also an introduction to the theory of martingales."
  2.  Backtracking: this section is the counterpart to section 7.2.1 which covered the generation of basic combinatorial patterns. This section covers non-basic patterns, ones where the developer needs to make tentative choices and then may need to backtrack when those choices need revision.
  3.  Dancing Links: this section is related to 2 above. It develops an important data structure technique that is suitable for backtrack programming described above.

My Blog List

Blog Archive


The views expressed on this blog are my own and do not necessarily reflect the views of Oracle.