Open Collections

Some new results on constructing optimal alphabetic binary trees

University of British Columbia

This thesis studies the question of whether optimal alphabetic binary trees can be constructed in o(n lg n) time. Hu and Tucker [1] gave the first subquadratic algorithm in 1971, namely an O(n lg n) time algorithm. Optimal alphabetic binary trees have many applications and the question of whether an o(n lg n) time algorithm exists has remained an open problem in data structures for the last 20 years. We show that a class of techniques for finding optimal alphabetic trees which includes all current methods yielding O(n lg n) time algorithms are at least as hard as sorting in whatever model of computation used. We introduce a new idea for finding optimal alphabetic binary trees which we refer to as region-processing. Region-processing methods have been successfully used to give O(n) time algorithms for the case where all the input weights are within a constant factor of one another and when they are exponentially separated. Although the region based method we give exhibits o(n lg n) time performance for many cases, we also show a reduction from sorting to it as well. It is possible that the ideas used in this reduction can be extended to yield a general ω(n) lower bound.

Thesis/Dissertation

application/pdf

2009-01-06

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/3384

Computer Science

University of British Columbia

UBCV

DSpace