[talks] W Mulzer general exam

[Melissa M Lawson]

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