Theory and Practice in Algorithm and Data Structure Design

Опубликовано 21 июня 2016, 19:20

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.