The Art of Don E. Knuth

Snuffy writes "Salon has a nice feature on our hero. It's a full length feature, talking about his long-term project writing of The Art of Computer Progamming "

Comments

10 sec. vs. 2^69 sec.

[geophile]

Saving 1 msec. is not what algorithm analysis is about. It's about taking 1 msec. to do something vs. 10 seconds or more. In 1 msec. you can go through the loop of a binary search, oh I don't know, 100 times, which means that you can search a list of 2^100 items. If you did a linear search, it would take you, on the average, 1/2 * 2^100 * (let's say 1 nanosecond) which is 2^69 seconds, which is a LONG time. This is the difference between O(log n) and O(n) for large values of n.

If you know n is small, (e.g. the number of lines in /etc/hosts), it won't matter what you do. If n is big, (e.g. a 100 meg log file), your choice of algorithm matters. If you're counting nanoseconds in a tight loop, then you're presumably already using a fast algorithm, but the exact variant is important. For example, heapsort is guaranteed O(n log n), but quicksort is often preferred because, although O(n^2) worst case, it's O(n log n) on the average, and the constant is lower than for heapsort. A lot of Knuth is about deriving these constants. Knuth goes even farther than this, e.g. showing how to derive the constants for different ways of choosing the pivot in a quicksort.

It's exhausting, non-productive and insane to apply this sort of analysis to everything. But once you've focused on the performance-critical parts of your program, Knuth's detailed analysis is essential.

The importance of algorithms and complexity

[ainvy]

As somebody who teaches algorithms and complexity, I should say that a good fraction of students seem disinterested in an good algorithms course. They are more interested in the syntax of C++ or Java than in developing their algorithmic skills. They somehow do not realize that any professional programmer should be able to pick a programming language in three to four days. (At least a good working knowledge.) What therefore distinguishes two programmers is how algorithmic one is.

I have also met many programmers in the industry who do not know what a Turing machine is and are surprised to hear that there such things as an unsolvable problem! After all, cannot a computer solve everything!? And of course, NP-completeness is some near mystical theory with no relevance.

This is the second article on Knuth in a week on /. This will probably enthuse more youngsters into taking algorithmics more seriously.

A short list of irrational geniuses

[Lucius Lucanius]

Being extremely brilliant in science or math does not mean that a person cannot be not irrational or religious. OTOH, being completely rational doesn't make one a brilliant mind either. Many accomplished genuises were extremely good in their field, and yet irrational in other respects.

* Godel came up with one the most elegant and logical proofs in math, yet in his later years was paranoid about being infected by microorganisms in his food and ended up starving to death. A notably illogical way to die.

* Ramanujan, who was self taught and considered one of the most brilliant mathematicians of the century, was devoutly religious and was eccentric enough that he carried a doctor's certificate stating he was sane.

* Emannuel Swedenborg was a deeply religious and profound scholar with an allegedly stupendous IQ.

* John Forbes Nash, who won the Nobel for a thesis he wrote at 21, became schizophrenic later. There's an unforgettable exchange in his biography, "A Beautiful Mind", by Sylvia Nasar (an excellent book).

Mackey: "How could you, a mathematician... believe that extraterrestrials are sending you messages?"

Nash: "Because, the ideas I had about supernatural beings came to me the same way that my mathematical ideas did. So I took them seriously."

Of course, this does not mean that Knuth or any genius is bound to be eccentric or worse. The point is - the history of math and science is replete with people of enormous logic, who were quite irrational and non-scientific outside their core field of accomplishment.

In any case, religion has more to do with faith and finding personal meaning, not with exhibiting scientifically rigorous proof (which would be quite irrational indeed, not to mention a career-limiting-move. )

L.

PS - found this thoughtful remark from Nash describing his delusions

http://www.nobel.se/laureates/economy-1994-2-aut obio.html

Thus further time passed. Then gradually I began to intellectually reject some of the delusionally influenced lines of thinking which had been characteristic of my orientation.This began, most recognizably, with the rejection of politically-oriented thinking as essentially a hopeless waste of intellectual effort.

So at the present time I seem to be thinking rationally again in the style that is characteristic of scientists. However this is not entirely a matter of joy as if someone returned from physical disability to good physical health. One aspect of this is that rationality of thought imposes a limit on a person's concept of his relation to the cosmos. For
example, a non-Zoroastrian could think of Zarathustra as simply a madman who led millions of naive followers to adopt a cult of ritual fire worship. But without his "madness" Zarathustra would necessarily have been only another of the millions or billions of human individuals who have lived and then been forgotten.

Statistically, it would seem improbable that any mathematician or scientist, at the age of 66, would be able through continued research efforts, to add much to his or her previous achievements. However I am still making the effort and it is conceivable that with the gap period of about 25 years of partially deluded thinking providing a sort of vacation my situation may be atypical. Thus I have hopes of being able to achieve something of value through my current studies or with any new ideas that come in the future.