[talks] S Yang general exam

[Melissa Lawson]

Siyu Yang will present her research seminar/general exam on Monday May 16 at 
2PM in Room 402.  The members of her committee are:  Bob Tarjan (advisor), 
Bernard Chazelle, and Sanjeev Arora.  Everyone is invited to attend her talk, and those
faculty wishing to remain for the oral exam following are welcome to do so.  Her 
abstract and reading list follow below.
--------------------------------------

On the Competitiveness of Binary Search Trees

Abstract:

I will present two results related to the competitiveness problem of binary search trees.

The first result is a heterogeneous finger search tree as a pure binary tree in which the
desired access and update time bounds hold in the worst case.  In a heterogeneous finger
tree, two fingers pointing to the minimum and the maximum keys in the tree are maintained,
and all operations on the binary search tree take running time logarithmic in the
distance to the closer finger.  We present a solution to this problem.  This solution can
be used to construct an O($\log\log n$)-competitive binary search tree with O($\log n$)
worst-case running time, simplifying an improvement to previous data structures by Demaine
et al.

I will also present an approach to proving that splay trees are O(loglogn)-competitive.
Such a result for splay trees would match the best competitive bound, which holds for
types of search trees specifically designed to achieve the bound. The dynamic optimality
conjecture for splay trees has been open for more than two decades, but no non-trivial
results have yet been proved. My approach to a proof uses a divide-and-conquer framework.

This is joint work with Robert Tarjan



Reading List:

[Book] 
Introduction to Algorithms.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.

[Papers]
Bose, P., Dou¨ieb, K., Dujmovi´c, V., Fagerberg, R.: An O(log log n)-competitive binary
search tree with optimal worst-case access times. In: Proc. 12th Scandinavian Symp. and
Workshop on Algorithm Theory. pp. 38–49 (2010) 

R. Cole. On the dynamic Finger conjecture for splay trees. part ii: The proof. SIAM
Journal on Computing, 30:2000.

R. Cole, B. Mishra, J. Schmidt, and A. Siegel. On the dynamic Finger conjecture for splay
trees. part i: Splay sorting log n-block sequences. SIAM Journal on Computing, 30:2000,
1995.

E. D. Demaine, D. Harmon, J. Iacono, and M. Patrascu. Dynamic optimality - almost. In
Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pages
484-490, Washington, DC, USA, 2004. IEEE Computer Society.

L. J. Guibas, E. M. McCreight, M. F. Plass, and J. R. Roberts. A new representation for
linear lists. In Proceedings of the ninth annual ACM symposium on Theory of computing,
STOC '77, pages 49-60, New York, NY, USA, 1977. ACM.

D. D. Sleator and R. E. Tarjan. Self-adjusting binary search trees. J. ACM, 32:652-686,
July 1985.

R. E. Tarjan. Sequential access in splay trees takes linear time. Combinatorica,
5:367-378, September 1985.

C. C. Wang, J. Derryberry, and D. D. Sleator. 2006. O(log log n)-competitive dynamic
binary search trees. In Proceedings of the seventeenth annual ACM-SIAM symposium on
Discrete algorithm (SODA '06). ACM, New York, NY, USA, 374-383.

R. Wilber. Lower bounds for accessing binary search trees with rotations. SIAM J. Comput.,
18:56-67, February 1989.