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. 3849 (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.