Robert Tarjan
Encyclopedia
Robert Endre Tarjan is a renowned American
computer scientist
. He is the discoverer of several important graph
algorithms, including Tarjan's off-line least common ancestors algorithm
, and co-inventor of both splay tree
s and Fibonacci heap
s. Tarjan is currently the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University
, and is also a Senior Fellow at Hewlett-Packard
.
, California
. His father was a child psychiatrist specializing in mental retardation, and ran a state hospital. As a child, Tarjan read a lot of science fiction, and wanted to be an astronomer
. He became interested in mathematics
after reading Martin Gardner
's mathematical games column in Scientific American
. He became seriously interested in math in the eighth grade, thanks to a "very stimulating" teacher.
While he was in high school, Tarjan got a job, where he worked IBM card punch collators. He first worked with real computers while studying astronomy at the Summer Science Program
in 1964.
Tarjan obtained a Bachelor's degree
in mathematics from the California Institute of Technology
in 1969. At Stanford University
, he received his Master's degree
in computer science in 1971 and a Ph.D.
in computer science (with a minor in mathematics) in 1972. At Stanford, he was supervised by Robert Floyd
and Donald Knuth
, both highly prominent computer scientists, and his Ph.D. dissertation was An Efficient Planarity Algorithm. Tarjan selected computer science as his area of interest because he believed that CS was a way of doing mathematics that could have a practical impact.
(1996).
Tarjan has vast industrial experience: he has worked at AT&T Bell Labs (1980-1989), InterTrust Technologies (1997-2001), Compaq (2002) and Hewlett Packard (2006-present). He has served on several ACM and IEEE committees, and has also been editor of several referreed journals.
Tarjan is known for his pioneering work on graph theory algorithms and data structures. Some of his well-known algorithms include the Tarjan's off-line least common ancestors algorithm
, and the Tarjan's strongly connected components algorithm
. The Hopcroft-Tarjan planarity testing
algorithm was the first linear-time algorithm for planarity-testing.
Tarjan has also developed important data structures such as the Fibonacci heap
(a heap data structure consisting of a forest of trees), and the splay tree
(a self-adjusting binary search tree; co-invented by Tarjan and Daniel Sleator
). Another significant contribution was the analysis of the disjoint-set data structure
; he was the first to prove the optimal runtime involving the inverse Ackermann function
.
jointly with John Hopcroft
in 1986. The citation for the award states that it was:
Tarjan was also elected an ACM Fellow in 1994. The citation for this award states:
Some of the other awards for Tarjan include:
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
computer scientist
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
. He is the discoverer of several important graph
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
algorithms, including Tarjan's off-line least common ancestors algorithm
Tarjan's off-line least common ancestors algorithm
In computer science, Tarjan's off-line least common ancestors algorithm is an algorithm for computing lowest common ancestors for pairs of nodes in a tree, based on the union-find data structure...
, and co-inventor of both splay tree
Splay tree
A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O amortized time. For many sequences of nonrandom operations, splay trees perform...
s and Fibonacci heap
Fibonacci heap
In computer science, a Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987...
s. Tarjan is currently the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
, and is also a Senior Fellow at Hewlett-Packard
Hewlett-Packard
Hewlett-Packard Company or HP is an American multinational information technology corporation headquartered in Palo Alto, California, USA that provides products, technologies, softwares, solutions and services to consumers, small- and medium-sized businesses and large enterprises, including...
.
Early life and education
He was born in PomonaPomona, California
-2010:The 2010 United States Census reported that Pomona had a population of 149,058, a slight decline from the 2000 census population. The population density was 6,491.2 people per square mile...
, California
California
California is a state located on the West Coast of the United States. It is by far the most populous U.S. state, and the third-largest by land area...
. His father was a child psychiatrist specializing in mental retardation, and ran a state hospital. As a child, Tarjan read a lot of science fiction, and wanted to be an astronomer
Astronomer
An astronomer is a scientist who studies celestial bodies such as planets, stars and galaxies.Historically, astronomy was more concerned with the classification and description of phenomena in the sky, while astrophysics attempted to explain these phenomena and the differences between them using...
. He became interested in mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
after reading Martin Gardner
Martin Gardner
Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...
's mathematical games column in Scientific American
Scientific American
Scientific American is a popular science magazine. It is notable for its long history of presenting science monthly to an educated but not necessarily scientific public, through its careful attention to the clarity of its text as well as the quality of its specially commissioned color graphics...
. He became seriously interested in math in the eighth grade, thanks to a "very stimulating" teacher.
While he was in high school, Tarjan got a job, where he worked IBM card punch collators. He first worked with real computers while studying astronomy at the Summer Science Program
Summer Science Program
The Summer Science Program is an intense six-week summer program for intellectually talented high school students. The program is based on a collaborative research project in celestial mechanics. Students study astronomy, physics, spherical trigonometry, and calculus while working to take...
in 1964.
Tarjan obtained a Bachelor's degree
Bachelor's degree
A bachelor's degree is usually an academic degree awarded for an undergraduate course or major that generally lasts for three or four years, but can range anywhere from two to six years depending on the region of the world...
in mathematics from the California Institute of Technology
California Institute of Technology
The California Institute of Technology is a private research university located in Pasadena, California, United States. Caltech has six academic divisions with strong emphases on science and engineering...
in 1969. At Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
, he received his Master's degree
Master's degree
A master's is an academic degree granted to individuals who have undergone study demonstrating a mastery or high-order overview of a specific field of study or area of professional practice...
in computer science in 1971 and a Ph.D.
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
in computer science (with a minor in mathematics) in 1972. At Stanford, he was supervised by Robert Floyd
Robert Floyd
Robert W Floyd was an eminent computer scientist.His contributions include the design of the Floyd–Warshall algorithm , which efficiently finds all shortest paths in a graph, Floyd's cycle-finding algorithm for detecting cycles in a sequence, and his work on parsing...
and Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
, both highly prominent computer scientists, and his Ph.D. dissertation was An Efficient Planarity Algorithm. Tarjan selected computer science as his area of interest because he believed that CS was a way of doing mathematics that could have a practical impact.
Computer science career
Tarjan has been teaching at Princeton University since 1985. He has also held academic positions at Cornell University (1972-73), University of California, Berkeley (1973-1975), Stanford University (1974-1980), and New York University (1981-1985). He has also been a fellow of the NEC Research Institute (1989-1997), a Visiting Scientist at the Massachusetts Institute of TechnologyMassachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
(1996).
Tarjan has vast industrial experience: he has worked at AT&T Bell Labs (1980-1989), InterTrust Technologies (1997-2001), Compaq (2002) and Hewlett Packard (2006-present). He has served on several ACM and IEEE committees, and has also been editor of several referreed journals.
Algorithms and data structures
Tarjan has designed many efficient algorithms and data structures for solving problems in a wide variety of application areas. He has published more than 228 refereed journal articles and book chapters.Tarjan is known for his pioneering work on graph theory algorithms and data structures. Some of his well-known algorithms include the Tarjan's off-line least common ancestors algorithm
Tarjan's off-line least common ancestors algorithm
In computer science, Tarjan's off-line least common ancestors algorithm is an algorithm for computing lowest common ancestors for pairs of nodes in a tree, based on the union-find data structure...
, and the Tarjan's strongly connected components algorithm
Tarjan's strongly connected components algorithm
Tarjan's Algorithm is a graph theory algorithm for finding the strongly connected components of a graph...
. The Hopcroft-Tarjan planarity testing
Planarity testing
In graph theory, the planarity testing problem asks whether, given a graph, that graph is a planar graph . This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures...
algorithm was the first linear-time algorithm for planarity-testing.
Tarjan has also developed important data structures such as the Fibonacci heap
Fibonacci heap
In computer science, a Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987...
(a heap data structure consisting of a forest of trees), and the splay tree
Splay tree
A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O amortized time. For many sequences of nonrandom operations, splay trees perform...
(a self-adjusting binary search tree; co-invented by Tarjan and Daniel Sleator
Daniel Sleator
Daniel Dominic Kaplan Sleator is a professor of computer science at Carnegie Mellon University. He discovered amortized analysis and he invented many data structures with Robert Tarjan, such as splay trees, link/cut trees, and skew heaps. He also pioneered the theory of link grammars and developed...
). Another significant contribution was the analysis of the disjoint-set data structure
Disjoint-set data structure
In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:* Find: Determine which set a particular element...
; he was the first to prove the optimal runtime involving the inverse Ackermann function
Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive...
.
Awards
Tarjan received the Turing AwardTuring Award
The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...
jointly with John Hopcroft
John Hopcroft
John Edward Hopcroft is an American theoretical computer scientist. His textbooks on theory of computation and data structures are regarded as standards in their fields. He is the IBM Professor of Engineering and Applied Mathematics in Computer Science at Cornell University.He received his...
in 1986. The citation for the award states that it was:
Tarjan was also elected an ACM Fellow in 1994. The citation for this award states:
Some of the other awards for Tarjan include:
- Nevanlinna PrizeNevanlinna PrizeThe Rolf Nevanlinna Prize is awarded once every 4 years at the International Congress of Mathematicians, for outstanding contributions in Mathematical Aspects of Information Sciences including:...
in Information Science (1983) - first recipient - National Academy of Sciences Award for Initiatives in ResearchNAS Award for Initiatives in ResearchThe NAS Award for Initiatives in Research is awarded annually by the National Academy of Sciences "to recognize innovative young scientists and to encourage research likely to lead toward new capabilities for human benefit. The award is to be given to a citizen of the United States, preferably no...
(1984) - Paris Kanellakis AwardParis Kanellakis AwardThe Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery to honor specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing...
in Theory and Practice, ACMAssociation for Computing MachineryThe Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
(1999) - Blaise Pascal Medal in Mathematics and Computer Science, European Academy of SciencesEuropean Academy of SciencesThe European Academy of Sciences has as mission to promote excellence in science and technology and their essential roles in fostering social and economic development and progress. It is registered in and operates under rules and regulations of Belgium. The European Academy of Sciences is an...
(2004) - Caltech Distinguished Alumni Award, California Institute of TechnologyCalifornia Institute of TechnologyThe California Institute of Technology is a private research university located in Pasadena, California, United States. Caltech has six academic divisions with strong emphases on science and engineering...
(2010)