Seminar by Robert E. Tarjan: Zip Trees

Robert E. Tarjan

  • Speaker: Robert E. Tarjan, Department of Computer Science, Princeton University and Intertrust Technologies
  • Title: Zip Trees
  • When: June 29, 2018 — 14:00
  • Where: I3S, Salle de conférence 007
  • Abstract: This talk will present the zip tree, a simple and efficient type of binary search tree. Zip trees use randomization to achieve balance. A zip tree can be viewed as a binary-tree representation of a skip list or as a variant of a treap. Insertion and deletion avoid the multiplicity of cases that arise in standard balanced trees. Zip trees can be adapted to exploit biased access distributions. Their simplicity makes them promising for concurrent use.

  • Short Bio: Since 1985, Robert E. Tarjan has been the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He previously held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, Intertrust Technologies, HP, and Microsoft. Among other honors, he received the Nevanlina Prize in Informatics, given by the International Mathematical Union, in 1982, and the A.C.M. Turing Award in 1986. He is a member of the National Academy of Sciences and the National Academy of Engineering, and a Fellow of the American Philosophical Society and the American Academy of Arts and Sciences. He has published over 250 papers, mostly in the areas of the design and analysis of data structures and graph and network algorithms.

  • See the thread on Twitter

Concurrent Disjoint Set Union

Robert E. Tarjan

  • Speaker: Robert E. Tarjan, Department of Computer Science, Princeton University and Intertrust Technologies
  • Title: Concurrent Disjoint Set Union — (watch the video)
  • When: December 9, 2016 — 10:30
  • Where: Inria Sophia Antipolis, amphi Kahn
  • Abstract: The disjoint set union problem is a classical problem in data structures with a simple and efficient sequential solution that has a notoriously complicated analysis. One application is to find strongly connected components in huge, implicitly defined graphs arising in model checking. In this application, the use of multiprocessors has the potential to produce significant speedups. We explore this possibility. We devise and analyze concurrent versions of standard sequential algorithms that use single and double compare-and-swap primitives for synchronization, making them wait-free. We obtain work bounds that grow logarithmically with the number of processors, suggesting the possibility of significant speedup in practice. This is ongoing joint work with Siddhartha Jayanti, an undergraduate at Princeton.

  • Short Bio: Since 1985, Robert E. Tarjan has been the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He previously held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, Intertrust Technologies, HP, and Microsoft. Among other honors, he received the Nevanlina Prize in Informatics, given by the International Mathematical Union, in 1982, and the A.C.M. Turing Award in 1986. He is a member of the National Academy of Sciences and the National Academy of Engineering, and a Fellow of the American Philosophical Society and the American Academy of Arts and Sciences. He has published over 250 papers, mostly in the areas of the design and analysis of data structures and graph and network algorithms.