Skip to content Skip to navigation
Qualifying Exam
5/6/2016 10:30 am
Hill 482

“Dynamic Optimality in Tournament Tree, a related Unordered Tree Model, for Tree Access Operations”

Yuanzhen Gu, Rutgers

Examination Committee: Chairman: Prof. Michael Fredman; Prof. William Steiger; Prof. Bahman Kalantari and Prof. Konstantinos Michmizos

Abstract

The Dynamic Optimality Conjecture states that given any access sequence, the cost of splay trees  applied on the access sequence is within a constant factor c of any other binary search tree (BST) for processing that access sequence. Despite more than 3 decades of research, the Dynamic Optimality Conjecture of BST is yet solved. After Wilber's theorem with rotations on BST been extended to unordered model, researchers have showed that dynamic optimality is unattainable in this extended model. However, when applied to tournament tree, a related but different unordered tree model, the prior existing proof is not applicable.

In this talk, we extend the work and explore the possibility of dynamic optimality upon tournament trees. After giving out the prerequisite theorem, we will discuss the framework design and proof strategy. Followed by the details of on-line and off-line implementation, along with applying encoding methods on augmented root-sequence. We demonstrated our result by constructing an adversary that generates access request sequences to elude efficient On-Line implementation while admitting efficient Off-Line implementation.  We'll conclude the work and indicate our further research topic at last.