DIKU Talk: Self-Adjusting Data Structures by Robert Tarjan

Title

Self-Adjusting Data Structures

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 on self-adjusting search trees and self-adjusting heaps.

Speaker

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 “outstanding contributions to mathematical aspects of information science,” and 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.

Host

Professor Mikkel Thorup, Head of the AC Section at the Department of Computer Science, UCPH.