Date: April 22nd
Time: 16:00 - 17:00

Optimal Binary Comparison Search Trees
Professor Mordecai Golin (CSE Dept, Hong Kong UST)

Historically, constructing optimal (minimum average search time)
binary search trees  (BSTs) is one of the canonical examples of 
dynamic programming.  In 1971, Knuth described how to solve this 
problem in O(n^2) time, with input specifying the probability of the 
different successful and unsuccessful searches.   While the trees 
constructed were binary, the comparisons used were ternary. 
Successful searches terminated at internal nodes and unsuccessful 
searches at leaves.

By contrast, in binary comparison trees  (BCSTs), internal nodes 
perform binary comparisons; the search branches left or right 
depending upon the comparison outcome and all searches terminating at 
leaves. Polynomial algorithms exist for solving the optimal BCST 
problem restricted to successful searches.  Hu and Tucker gave an O(n 
log n) algorithm when all comparisons are the inequality “<”;  
Anderson et. al. developed an O(n^4) algorithm when both “<” and “=” 
comparisons are allowed.

In this talk we present the first polynomial time algorithms for 
solving the optimal BCST  problem when unsuccessful searches are 
included in the input and any set of comparisons are permitted. Our 
running times depend upon the comparisons allowed.  If equality is 
not allowed, our algorithm runs in O(n log n) time; if equality is 
allowed, O(n^4). We also demonstrate O(n) time algorithms that yield 
almost optimal binary comparison trees, with tree cost within 
constant additive factor of optimal.

This is joint work with Marek Chrobak,  Ian Munro and Neal Young. 

(Host: Osamu Watanabe)