Questions for Donald Knuth • Hacker News Board

Re: Questions for Donald Knuth

#41

Post by jamesmiller5 » Wed, May 21, 2014, 6:29 AM UTC

jallmann wrote: post #30

YAYERKA wrote: post #14

What 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. [1…

I believe tilde notation is meant to bridge the gap between a pure mathmatical behaviour analysis and realistic expectations when using an algorithm. Analysing an algorithm and determining that say for 2x input size expect 8x resource usage gives more information that would otherwise be hidden in big O notation.

http://introcs.cs.princeton.edu/java/41analysis/

Re: Questions for Donald Knuth

#42

Post by laichzeit0 » Wed, May 21, 2014, 6:55 AM UTC

justin66 wrote: post #29

The 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.

The excellent book "C Interfaces and Implementations: Techniques for Creating Reusable Software" by David Hanson as well as "A Retargetable C Compiler: Design and Implementation" by the same author are both written in the literate programming style.

I'd definitely say it's unpopular, but hardly goofy from a pedagogical point of view. C Interfaces and Implementations is such a beautiful book and the literate programming style really compliments it well.

Re: Questions for Donald Knuth

#43

Post by laichzeit0 » Wed, May 21, 2014, 7:02 AM UTC

thebear wrote: post #26

Given 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?

Some quotes of Knuth on functional programming:

"Out of the ~250 programs I wrote last year, 2-3 would have benefited from being written in a functional style."

"With 1 or even 2 hands tied behind your back it’s hard to do anything dangerous."

I remember looking this up once and couldn't find much. I guess he figures everything that can be written in functional style can be written in imperative style so why bother.

Re: Questions for Donald Knuth

#44

Post by noselasd » Wed, May 21, 2014, 8:37 AM UTC

reedlaw wrote: post #20

ghswa wrote: post #7

"I did write a compiler manual in 1958, which by chance was actually used as the textbook for one of my classes in 1959(!)" How many people in the world could claim something similar?

When I first read that, I assumed he was teaching the class. But after checking Wikipedia I found that he received his bachelor of science degree in 1960. Now I'm astonished.

Yes, that makes it a bit more remarkable - As I remember at least 3 classes at Uni where the professor wrote the book we were using.

Re: Questions for Donald Knuth

#45

Post by Athas » Wed, May 21, 2014, 9:07 AM UTC

thebear wrote: post #26

Given 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?

Most algorithms guys don't seem to be that enthusiastic about functional programming. My personal theory is that functional programming is more rooted in abstract logic, which isn't what algorithms is really about.

Re: Questions for Donald Knuth

#46

Post by sytelus » Wed, May 21, 2014, 10:00 AM UTC

Thanks for sharing. This is just amazing!

Few favorite tidbits:

- Only 2% of population seem to have aptitude for computer science

- Knuth writes 2 programs per week even today

- He is leaning towards P=NP

- Most software projects fails because they are not entrusted to geeks

- 50 years in writing 3000 page bible of CS. I would suppose it takes probably same time to read all of that material.

Re: Questions for Donald Knuth

#47

Post by olalonde » Wed, May 21, 2014, 10:48 AM UTC

justin66 wrote: post #29

The 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.

Wouldn't those be examples of literate programming? http://coffeescript.org/documentation/docs/grammar.html http://underscorejs.org/docs/underscore.html

Re: Questions for Donald Knuth

#48

Post by Intermernet » Wed, May 21, 2014, 11:42 AM UTC

I found the reply to Robert Tarjan interesting, and I wonder how many people who conduct programmer job interviews would have guessed that the Big O derived value vs the actual performance of the algorithm would be so unpredictable!

"Another issue, when we come down to earth, is the efficiency of algorithms on real computers. As part of the Stanford GraphBase project I implemented four algorithms to compute minimum spanning trees of graphs, one of which was the very pretty method that you developed with Cheriton and Karp. Although I was expecting your method to be the winner, because it examines much of the data only half as often as the others, it actually came out two to three times worse than Kruskal's venerable method. Part of the reason was poor cache interaction, but the main cause was a large constant factor hidden by O notation."

Question: in what ways can having a large constant factor in an algorithm cause such a dramatic performance difference on modern hardware. Can anyone give examples? I can only assume that the "large" constant factor in this example was large enough to be always overflowing, and needed some bignum functions to work.

Re: Questions for Donald Knuth

#49

Post by Intermernet » Wed, May 21, 2014, 11:48 AM UTC

jamesmiller5 wrote: post #41

jallmann wrote: post #30

Earlier quoted context omitted.

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. [1…

I believe tilde notation is meant to bridge the gap between a pure mathmatical behaviour analysis and realistic expectations when using an algorithm. Analysing an algorithm and determining that say for 2x input size expect 8x resource usage gives more information that would otherwise be hidden in big O notation. http://introcs.cs.princeton.edu/java/41analysis/

Thankyou, you in part answered my question elsewhere in this thread.

I'll give it a read.

Re: Questions for Donald Knuth

#50

Post by acqq » Wed, May 21, 2014, 12:34 PM UTC

jbapple wrote: post #23

This 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…

I think you misunderstood him. I believe he knows he can prove that the recurrence finishes, he can't prove that the recurrence he writes is the mathematically right description of the problem he observes.