University of British Columbia
Some new results on constructing optimal alphabetic binary trees
Abstract
dc:descriptionThis 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.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 1992
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Mumey, Brendan M.
Rights
dc:rights- Statement dc:rights
-
- 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.
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/3384