Robert Endre Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University, which he joined in 1985. His Princeton faculty profile records the 1986 ACM A.M. Turing Award, which he shared with John Hopcroft “for fundamental achievements in the design and analysis of algorithms and data structures,” along with his election to the National Academy of Sciences and the National Academy of Engineering.
Tarjan is responsible for a remarkable number of the algorithms taught in any data-structures course. He devised efficient depth-first-search methods for finding strongly connected components and biconnected components of a graph, analyzed the union-find disjoint-set structure to near-constant time per operation, and co-invented splay trees, link-cut trees, and the Fibonacci heap. The Fibonacci heap in turn sped up classic graph algorithms for shortest paths and minimum spanning trees.
Among his most influential contributions is amortized analysis, a way of measuring the average cost of an operation across a whole sequence rather than the worst case of a single operation. His 1985 paper “Amortized Computational Complexity,” hosted in scanned form by Princeton, surveys the technique and shows how designing for low amortized cost yields “self-adjusting” data structures that are simple, flexible, and efficient.
His Princeton profile also notes that he was the first winner of the Rolf Nevanlinna Prize from the International Mathematical Union. Across decades of work, Tarjan’s combination of clever data structures and rigorous analysis has shaped how the field designs and reasons about algorithms.