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)

Title:
Optimal Search Trees with 2-way Comparisons

Abstract:
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.