11 of 20 people found the following review helpful
Volume 4A Interesting; Excellent On Exhaustive Search Techniques; For Hamiltonian Path AKA P-NP Topics We Await Volume 4B!,
Verified Purchase(What's this?)
This review is from: The Art of Computer Programming, Volumes 1-4A Boxed Set (Hardcover)
Since receipt of volume 4A two days ago, I have been dipping into this and that topic via the indexes ...
What an excellent authoritive masterful survey - up to 2011 - of combinatorial exhaustive search techniques ...
And, some focus on application to business usable sorting and searching techniques ...
Excellent and comprehensive chapter on bitwise tips and techniques, and all sorts of other obscure techniques such as resolution and radix sorting that may not be obvious to information systems graduates who don't have to study algorithms in depth.
(Must confess I've seen earlier editions of volumes 1 to 3 before!)
Donald Knuth is not averse to explaining some things in terms of history or heuristic ... the only heuristic explanation I'm familiar with he doesn't raise are the ones based on the laws of thermodynamics. There is this argument that to understand sorting algorithms one must consider the entrophy gains and losses as the system becomes more ordered and the consequent radiated heat somewhere else in the universe. The related argument from nuclear cell division DNA replication - in science fiction called sometimes the life force - is that when one duplicates information there is a consequent 'life force' heat side effect from the physical law of the conservation of information in quantum mechanics equations. The heuristic explanation then is that if we can minimise the heat from the sorting, we'll have found the best sorting algorithm. Now quicksort wastes more fractions of distinguishment than multi-pass-N-way merge sorting in theory ... so there is more tiny fractions of wasted bits caused by the comparisions. If the exchanges are free and there is unlimited memory then less wasted bit fractions of distinguishment would mean less heat therefore quicksort should on average be slower ... but practical tests proves quicksort faster!
That's the problem with heuristics!
However, reading through some fo Knuth's essays on exhaustive searching may suggest a solution ... that if we have 64K 32 bit integers, to minimise comparisions we precompute all partitions of the 64K into several thousand sequences of varying length less than length 17, use table driven state machines to optimally sort these sequences in place, and check each resultant multi-pass-N-way merge sort for total wasted bits of distinguishment to find the best breakdown to compare quicksort with. This impossible to conduct experiment would then show the validity or invalidity of applying thermodynamics to the problem ...
Unfortunately for me I bought this volume hoping to get a survey of the latest news on the P-NP completeness problem. I will have to await volume 4B for that!