Conversations: Jon Bentley
Dr. Dobb's Journal (03/31/08) Blake, Deirdre
Avaya Labs research scientist Jon Bentley is currently working on a mathematical theory of authentication that can quantify the assurance of security secrets. Bentley says that his 1976 Ph.D. thesis included a section in which he attempted to describe the process of designing an algorithm, and that he believes his approach has stood the test of time. "The principles include generalizing, using high-level and abstract description of algorithms, examining degenerate cases, and employing standard speed-up tricks," says Bentley. Before getting immersed in the details of designing an algorithm, Bentley says, the most important step is to find out what the real problem is. Bentley says that sometimes algorithm design and algorithm analysis proceed hand-in-hand, such as when students design an algorithm so that it can be analyzed. The purpose of algorithm design is to develop a good algorithm, while the purpose of algorithm analysis is to understand how good an algorithm is. "Sometimes, though, people design algorithms and report that they are fast without analyzing their runtime," he says. "What a delightful challenge for an algorithm analyst! I've walked both sides of that street. My most frequently cited paper was for the 1975 ACM Undergraduate Student Paper competition; it introduced multidimensional binary search trees, which Don Knuth called 'k-d trees.' I described an algorithm for nearest-neighbor searching, but I couldn't even begin to analyze it. Many folks have made great progress on the analysis since then." He says programming is subtle, that we must learn to be "humble programmers," and that there are lot of tools available, including precise specifications, formal methods, and extensive tests. Bentley adds, however, that one of the best tools is the eyes of really smart friends.
Click Here to View Full Article
No comments:
Post a Comment