Haifa University - Dept. of CS Theory Seminar
Speaker : Oren Weimann, MIT.
Title: "Finding an Optimal Tree Searching Strategy in Linear Time"
Date: Thursday, Nov. 15.
Place: Haifa U. Education Building, room 570.
Time: 12:15 - 13:30
Abstract:
We address the extension of the binary search technique
from sorted arrays and totally ordered sets to trees
and tree-like partially ordered sets. As in the sorted
array case, the goal is to minimize the number of
queries required to find a target element in the worst
case. However, while the optimal strategy for searching
an array is straightforward (always query the middle
element), the optimal strategy for searching a tree is
dependent on the tree's structure and is harder to
compute. We present an O(n)-time algorithm that
finds the optimal strategy for binary searching a tree,
improving the previous best O(n3)-time algorithm. The
significant improvement is due to a novel approach for
computing subproblems, as well as a method for reusing
parts of already computed subproblems, and a linear-
time transformation from a solution in the form of
an edge-weighed tree into a solution in the form of a
decision tree.