"Most of the techniques that have turned out to be important were originally introduced for the wrong reasons!"
How inappropriate.
Questions for Donald Knuth
21–30 of 61 posts
Re: Questions for Donald Knuth
#22In the Q&A Knuth mentions TAOCP conversion to ebook several times - I did a quick search and found only millions of pirate sites. Does anyone know the legitimate source where the ebook can be bought? Informit seemed likely but there are only two digital volumes available there. (edit: there is a note saying "as they become available". I guess TAOCP is only partially portable so far, more to come.) (brag: I got a deci…
His personal page appears to have a link to the "approved" ebooks (http://www.informit.com/store/art-of-computer-programming-vo...).
Re: Questions for Donald Knuth
#23This part confused me:
"My job is to go beyond correctness, to an analysis of such things as the program's running time: I write down a recurrence, say, which is supposed to represent the average number of comparisons made by that program on random input data. I'm 100% sure that my recurrence correctly describes the program's performance, and all of my colleagues agree with me that the recurrence is "obviously" valid. Yet I have no formal tools by which I can prove that my recurrence is right. I don't really understand my reasoning processes at all! My student Lyle Ramshaw began to create suitable foundations in his thesis (1979), but the problem seems inherently difficult."
There are formal tools to prove recurrences are correct.
First, any proof assistant like Coq or Isabelle could be used to verify recurrences.
Papers like "A Machine-Checked Proof of the Average-Case Complexity of Quicksort in Coq" show that this is not limited to just the recurrence, but can also be applied to programs and random input data. The Certified Complexity (CerCo) project does similar work.
Maybe I misunderstood what Knuth meant by "formal tools" or "recurrence is right". Here is a link to the abstract of Ramshaw's thesis:
http://oai.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=ht...
Re: Questions for Donald Knuth
#24In the Q&A Knuth mentions TAOCP conversion to ebook several times - I did a quick search and found only millions of pirate sites. Does anyone know the legitimate source where the ebook can be bought? Informit seemed likely but there are only two digital volumes available there. (edit: there is a note saying "as they become available". I guess TAOCP is only partially portable so far, more to come.) (brag: I got a deci…
I've seen 3 volumes recently posted on Safari Books Online
Re: Questions for Donald Knuth
#25Re: Questions for Donald Knuth
#26Given the facts that functional programming has been all the rage lately, and that advocates of functional programming tend to emphasize its mathematical roots, I would find it interesting to get Donald Knuth's take on the subject. Web search came up empty for me. Does anybody know of any statements he's made on functional programming?
Re: Questions for Donald Knuth
#27In the Q&A Knuth mentions TAOCP conversion to ebook several times - I did a quick search and found only millions of pirate sites. Does anyone know the legitimate source where the ebook can be bought? Informit seemed likely but there are only two digital volumes available there. (edit: there is a note saying "as they become available". I guess TAOCP is only partially portable so far, more to come.) (brag: I got a deci…
I found seven in my University's books, but they'd all been corrected by the time I handed them in.
I hope you framed that check!
Re: Questions for Donald Knuth
#28I've been to couple of Donald Knuth's Christmas Tree Lectures. While he was signing my copy of 'TAOCP Volume 1', I asked him if he thought anyone in the world had read all of TAOCP, himself excluded. I didn't clarify, but he seemed to assume (correctly) that by 'read' I meant 'read and comprehended.' His reply was yes, but not many. He mentioned a guy in Germany who goes over his books again and again looking for err…
>His reply was yes, but not many. He mentioned a guy in Germany who goes over his books again and again looking for errors.
I call these types of people "moles" because I imagine they basically never see daylight. Thank god for these people. If I ever have the time and will power to study TAOCP it will be a very relaxed mindset, knowing that with a high probability I can be confident that the book, exercises and solutions are error free.
Re: Questions for Donald Knuth
#29The unpopularity and inherent goofiness of literate programming, and the way Knuth always mentions it in interviews, feels like a sort of elephant in the room whenever a new interview appears.
Re: Questions for Donald Knuth
#30What an amazing exchange of ideas; Knuths response to Tarjans Q15 was particularly interesting since he was able to illustrate his insight with a concrete example; >Thus I think the present state of research in algorithm design misunderstands the true nature of efficiency. The literature exhibits a dangerous trend in contemporary views of what deserves to be published. > Another issue, when we come down to earth, is…
Reading that was rather vindicating. The same concern is raised by phk in his B-heap essay [1], where he criticizes Knuth for the exact same reason -- that algorithm analysis has become disconnected from the characteristics of the underlying hardware.
While phk has a point, the dig at Knuth's work feels a bit unfair. In any case, I'm curious to see whether future editions of TAOCP note this caveat in its analysis.