4 ms·
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 exam
by YAYERKA 12y ago
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 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.
- jallmann 12y agoReading 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] http://queue.acm.org/detail.cfm?id=1814327 http://queue.acm.org/detail.cfm?id=1814327
- jamesmiller5 12y agoI 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/ http://introcs.cs.princeton.edu/java/41analysis/
- Intermernet 12y agoThankyou, you in part answered my question elsewhere in this thread. I'll give it a read.
- neic 12y agoDo you know of any resources that teaches this? I'm looking for a hypothetical book like "CLRS for VMs".