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.