Theory and Practice in Algorithm and Data Structure Design

June 20, 2014
Tarjan Robert | Microsoft Research SVC

In the study and use of algorithms, theory and practice interact, as do algorithm and data structure design. To illustrate this, I’ll discuss recent theoretical and practical results on the problem of finding dominators in a flow graph and on the disjoint set union problem. The former is an important basic computation in optimizing compilers; the latter is a classical problem in data structures with diverse applications. Fast algorithms to find dominators rely on disjoint set union algorithms and extensions. In practice, simple versions of these algorithms beat theoretically faster ones. A theoretical analysis of a randomized disjoint set union algorithm provides an explanation of these empirical results.

Speaker Details

Robert E Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University and a Visiting Researcher at MSR SVC. He is an expert in the design and analysis of data structures and graph algorithms, and invented or co-invented many of the most efficient methods for a variety of fundamental problems, including search, disjoint set maintenance, testing planarity, finding graph components, and finding minimum spanning trees, shortest paths, maximum matchings, and maximum flows. He received his B.S. in Mathematics from the California Institute of Technology in 1969 and his Ph.D. in Computer Science from Stanford in 1972. He is a member of the National Academy of Sciences, the National Academy of Engineering, the American Philosophical Society, and the American Academy of Arts and Sciences. He has won numerous awards, including the Nevanlinna Prize and the Turing Award.