Seminar: Mysteries of Search Trees

Dr. Robert E. Tarjan (Princeton University)

May 14, 2013, 11:00am, H 767

Abstract

The search is one of the most basic and most important data structures in computer science. It lies behind all modern database systems and has many other applications. Although the history of this data structure extends back more than fifty years, we still do not know everything about it. This talk will explore new ideas that lead both to simpler kinds of search trees and to a better analysis of their efficiency.

Bio

Robert E. Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University and a Visiting Researcher at Microsoft Research. He is an expert in the design and analysis of data structures and graph algorithms. A member of the U.S. National Academy of Sciences and of the U.S. National Academy of Engineering, he was awarded the Nevanlinna Prize in 1982, and, with John Hopcroft, the Turing Award in 1986.