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

Bio: 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