Wolfgang Mulzer will present his research seminar/general exam on Wednesday May 2 at 2PM in Room 402. The members of his committee are Bernard Chazelle (advisor), Bob Tarjan, and Moses Charikar. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. -------------------------------- Abstract: In recent years, algorithm designers have been confronted with the task of developing algorithms that must be able to cope with larger and larger amounts of data. Traditional algorithms based on worst-case analysis show limitationsand new approaches, more focused on data are called for. The data we encounter in practice tends to have more structure than is usually assumed by traditional worst-case approaches, and it might be possible to exploit this additional structure to design better algorithms for classical problems. As an example, we consider the classical UNION-SPLIT-FIND-problem in which we need to maintain a dynamic set S of elements from an ordered universe and to efficiently find the successor in S of any given element in the universe. This problem has been widely studied in the literature and there are optimal algorithms for it both in the pointer-machine and the RAM model of computation. We add the following twist: Instead of allowing arbitrary operations on the set S, we are given a directed graph G of constant degree whose nodes are labeled with queries to the data structure. Any query sequence is generated by a walk in G. We give a simple algorithm that answers all queries in constant time with sub-quadratic space for the case that G is a path. We investigate whether, for more complicated graphs, the classical lower bounds might still hold. Reading List: K. Mehlhorn, S. Naeher, H. Alt. A lower bound on the complexity of the union-split-find problem. SICOMP 17(6), 1988 H. Gabow, R. E. Tarjan, A linear-time algorithm for a special case of disjoint set union. JCSS 30(2), 1985. J. La Poutre. Lower bounds for the union-find and split-find problem on pointer machines. STOC 1990 C. Kenyon and V. King. On boolean decision trees with faulty nodes. Random Structures and Algorithms 5(3), 1994. M. Fredman. How good is the information theory bound in sorting. Theoretical Computer Science 1, 1976. M. Mitzenmacher, E. Upfal, Probability and Computing, Chapters 7, 9, 11 R. Motwani, P. Raghavan, Randomized Algorithms, Chapters 6, 8, 13 M. de Berg, M. van Kreveld, M. Overmars, O. Scharzkopf, Computational Geometry: Algorithms and Applications, Chapter 11