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.
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.
Launched in 2012, the Colloquium d’Informatique de Sorbonne Université is a recurring event that invites major figures of the computer science field to give special lectures on the campus of Sorbonne University’s Science and Engineering Faculty. It targets a diverse yet technically-informed audience, and especially computer science researchers from all specialities, PhD students, and computer science students at master level.
The Colloquium’s main event is the invited speaker’s lecture, a 45-minute talk followed by questions and interactions with the audience. Generally, this lecture is associated with a masterclass reserved for PhD students from LIP6 and/or other labs.
As the main driving force behind to the steering committee, LIP6 oversees the Colloquium’s organisation, with occasional support from ISIR.