Algorithms & Randomness Center (ARC)
Ian Munro – University of Waterloo
Monday, February 1, 20116
Klaus 1116 West - 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Optimal Search Trees with 2-way Comparisons
This talk is about finding a polynomial time algorithm that you probably thought was known almost a half century ago, but it wasn’t. The polynomial time algorithm is still rather slow and requires a lot of space to solve, so we also look at extremely good and fast approximate solutions. More specifically …
In 1971, Knuth gave an O(n2)-time algorithm for the now classic problem of finding an optimal binary search tree. Knuth’s algorithm works only for search trees based on 3-way comparisons, but most modern programming languages and computers support only 2-way comparisons (<, = and >). Until this work, the problem of finding an optimal search tree using 2-way comparisons remained open — polynomial time algorithms were known only for restricted variants. We solve the general case, giving
(i) an O(n4)-time algorithm and
(ii) a linear time algorithm that gives a tree with expected search cost within 2 comparisons of the optimal.
This is joint work with Marek Chrobak, Mordecai Golin, and Neal E. Young.