Robert Tarjan facts for kids
Quick facts for kids
Robert Tarjan
|
|
|---|---|
 |
|
| Born |
Robert Endre Tarjan
April 30, 1948 Pomona, California, U.S.
|
| Education | California Institute of Technology (BS) Stanford University (MS, PhD) |
| Known for | Algorithms and data structures |
| Awards | Paris Kanellakis Award (1999) Turing Award (1986) Nevanlinna Prize (1982) |
| Scientific career | |
| Fields | Computer science |
| Institutions | Princeton University New York University Stanford University University of California, Berkeley Cornell University Microsoft Research Intertrust Technologies Hewlett-Packard Compaq NEC Research Bell Labs |
| Thesis | An Efficient Planarity Algorithm (1972) |
| Doctoral advisor | Robert W. Floyd |
| Other academic advisors | Donald Knuth |
| Doctoral students |
|
Robert Endre Tarjan, born on April 30, 1948, is a famous American computer scientist and mathematician. He is known for creating many important ways to solve problems using computers, especially in an area called graph theory. These problem-solving methods are called algorithms.
He helped invent the strongly connected components algorithm. He also co-invented special ways to organize data, like splay trees and Fibonacci heaps. Mr. Tarjan is currently a distinguished professor of Computer Science at Princeton University.
Contents
Early Life and Education
Robert Tarjan was born in Pomona, California. His father, George Tarjan, was a child psychiatrist. He specialized in helping children with mental challenges. Robert's younger brother, James, became a chess grandmaster.
As a child, Robert loved reading science fiction. He even wanted to be an astronomer. He became interested in mathematics after reading about math games. These games were in a magazine column by Martin Gardner. He got really into math in eighth grade. This was thanks to a "very stimulating" teacher.
While in high school, Tarjan worked with IBM punch card machines. These were early tools for handling data. He first used real computers in 1964. This was during a program where he studied astronomy.
Mr. Tarjan earned his first degree in mathematics in 1969. He studied at the California Institute of Technology. He then went to Stanford University. There, he earned a master's degree in computer science in 1971. He also got his Ph.D. (a very high degree) in computer science in 1972. His main teachers at Stanford were Robert W. Floyd and Donald Knuth. They are both very famous computer scientists. His Ph.D. project was about an efficient way to check if a graph can be drawn without lines crossing.
Tarjan chose computer science because he saw it as a way to use math. He believed it could have a real-world impact. Today, he lives in Princeton, New Jersey, and Silicon Valley. He is married to Nayla Rizk. They have three daughters: Alice, Sophie, and Maxine.
Computer Science Career
Robert Tarjan has been teaching at Princeton University since 1985. He has also taught at other top universities. These include Cornell University, University of California, Berkeley, Stanford University, and New York University.
He also worked at the NEC Research Institute for several years. In 2013, he joined Microsoft Research Silicon Valley. In 2014, he returned to Intertrust Technologies as their chief scientist. He has also worked at AT&T Bell Labs, Compaq, and Hewlett Packard.
Important Algorithms and Data Structures
Mr. Tarjan is famous for his groundbreaking work. This work is in graph theory algorithms and data structures. Graph theory is a part of math that studies networks. Data structures are ways to organize information in computers.
Some of his well-known algorithms include:
- Tarjan's off-line least common ancestors algorithm: This helps find common ancestors in a tree-like structure.
- Tarjan's strongly connected components algorithm: This finds groups of connected parts in a graph.
- Tarjan's bridge-finding algorithm: This finds "bridges" in a graph. A bridge is a connection that, if removed, would split the graph into two parts.
He also helped create the "median of medians" algorithm. This is a fast way to find the middle value in a list. The Hopcroft–Tarjan algorithm was the first fast way to check if a graph can be drawn without lines crossing.
Tarjan also developed important data structures. These include:
- Fibonacci heap: This is a special way to store data. It helps computers find the smallest item very quickly.
- Splay tree: This is a type of binary search tree. It automatically adjusts itself to be efficient. He invented this with Daniel Sleator.
Another big contribution was his work on the disjoint-set data structure. He was the first to prove how fast it could work.
Awards and Recognition
Robert Tarjan has received many important awards for his work.
In 1986, he won the Turing Award with John Hopcroft. This award is like the Nobel Prize for computer science. The award recognized them:
For fundamental achievements in the design and analysis of algorithms and data structures.
He was also chosen as an ACM Fellow in 1994. This honor is given to members of the Association for Computing Machinery. The award recognized him:
For seminal advances in the design and analysis of data structures and algorithms.
Other awards Mr. Tarjan has received include:
- Nevanlinna Prize in Information Science (1983) – He was the very first person to receive this award.
- Member of the American Academy of Arts and Sciences, elected 1985.
- National Academy of Sciences Award for Initiatives in Research (1984).
- Member of the National Academy of Sciences, elected 1987.
- Member of the National Academy of Engineering, elected 1988.
- Member of the American Philosophical Society, elected 1990.
- Paris Kanellakis Award in Theory and Practice, from the ACM (1999).
- Caltech Distinguished Alumni Award, from the California Institute of Technology (2010).
Selected Publications
Mr. Tarjan has written many important research papers. His papers have been referenced by other scientists over 94,000 times. Some of his most referenced papers include:
- 1972: "Depth-first search and linear graph algorithms," which appeared in the SIAM Journal on Computing.
- 1987: "Fibonacci heaps and their uses in improved network optimization algorithms," co-authored with M.L. Fredman, published in the Journal of the ACM.
- 1983: "Data structures and network algorithms," a book published by the Society for Industrial and Applied Mathematics.
- 1988: "A new approach to the maximum-flow problem," co-authored with V. Goldberg, published in the Journal of the ACM.
Patents
Robert Tarjan holds at least 18 U.S. patents. These are legal rights that protect his inventions. Some of these patents include:
- J. Bentley, D. Sleator, and R. E. Tarjan, U. S. Patent 4,796,003, about "Data Compaction," from 1989.
- N. Mishra, R. Schreiber, and R. E. Tarjan, U. S. Patent 7,818,272, about finding "clusters of objects in an arbitrary undirected graph," from 2010.
- B. Pinkas, S. Haber, R. E. Tarjan, and T. Sander, U. S. Patent 8220036, about "Establishing a secure channel with a human user," from 2012.
See also
In Spanish: Robert Tarjan para niños
