Colloquium d’Informatique de Sorbonne Université
Robert E. Tarjan, Princeton University

Wednesday, June 15, 2022 18:00
Amphi Durand Sorbonne University - Faculté des Sciences

Self-Adjusting Data Structures

Robert Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He has held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, HP, Microsoft, and Intertrust Technologies. He has invented or co-invented many of the most efficient known data structures and graph algorithms. He was awarded the first Nevanlinna Prize from the International Mathematical Union in 1982 for “for outstanding contributions to mathematical aspects of information science,” the Turing Award in 1986 with John Hopcroft for “fundamental achievements in the design and analysis of algorithms and data structures,” and the Paris Kanellakis Award in Theory and Practice in 1999 with Daniel Sleator for the invention of splay trees. He is a member of the U.S. National Academy of Sciences, the U. S. National Academy of Engineering, the American Academy of Arts and Sciences, and the American Philosophical Society.

Abstract

Data structures are everywhere in computer software. Classical data structures are specially designed to make each individual operation fast. A more flexible approach is to design the structure so that it adapts to its use. This idea has produced data structures that perform well in practice and have surprisingly good performance guarantees. In this talk I’ll review some recent work on such data structures, specifically the splay tree, a self-adjusting binary search tree, and the SLIM HEAP, a self-adjusting priority queue.