Robert Tarjan facts for kids
Quick facts for kids
Robert Tarjan
|
|
|---|---|
 |
|
| Born |
Robert Endre Tarjan
April 30, 1948 Pomona, California, United States
|
| Alma mater | 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 an American computer scientist and mathematician. He is famous for creating many important algorithms. These algorithms help computers solve problems faster. He also helped invent special ways to organize data, like splay trees and Fibonacci heaps. Today, Tarjan is a professor of Computer Science at Princeton University.
Contents
Early Life and School
Robert Tarjan was born in Pomona, California. His father, George Tarjan, was a doctor who helped children with mental health issues. Robert's younger brother, James, became a chess grandmaster.
When Robert was a kid, he loved reading science fiction books. He even wanted to be an astronomer! He became interested in mathematics after reading a fun math column in a magazine. In eighth grade, a "very stimulating" teacher made him love math even more.
While in high school, Tarjan worked with old-fashioned IBM punch card machines. He first used real computers in 1964. This was during a special program for young scientists.
College and Beyond
Tarjan went to the California Institute of Technology and earned a degree in mathematics in 1969. Then, he went to Stanford University. There, he got his master's degree in computer science in 1971. He also earned his Ph.D. (a very high degree) in computer science in 1972.
At Stanford, he learned from famous computer scientists like Robert W. Floyd and Donald Knuth. His Ph.D. project was about finding an efficient way to test if a graph could be drawn on a flat surface without lines crossing. Tarjan chose computer science because he saw it as a way to use math to solve real-world problems.
Today, Tarjan lives in Princeton, New Jersey, and also in Silicon Valley. He is married to Nayla Rizk and has three daughters: Alice, Sophie, and Maxine.
Computer Science Work
Since 1985, Robert Tarjan has been teaching at Princeton University. He has also taught at other top universities. These include Cornell University, University of California, Berkeley, Stanford University, and New York University.
He has also worked for many technology companies. These include AT&T Bell Labs, Intertrust Technologies, Compaq, and Hewlett Packard. In 2013, he joined Microsoft Research. In 2014, he returned to Intertrust Technologies as their chief scientist.
Amazing Algorithms and Data Structures
Tarjan is well-known for his groundbreaking work on graph theory algorithms. Graphs are like networks of points and lines. His algorithms help computers understand these networks.
Some of his famous 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 points in a graph that are all connected to each other.
- Tarjan's bridge-finding algorithm: This identifies "bridges" in a graph. A bridge is a connection that, if removed, would split the graph into two separate parts.
He also helped create the median of medians algorithm. This algorithm quickly finds the middle value in a list of numbers. The Hopcroft–Tarjan planarity testing algorithm was the first to quickly check if a graph could be drawn without lines crossing.
Tarjan also developed important ways to store and organize data. These are called data structures.
- The Fibonacci heap is a special way to organize data in a tree-like structure.
- The splay tree is a "self-adjusting" tree. It changes itself to make finding information faster. Tarjan invented this with Daniel Sleator.
- He also studied the disjoint-set data structure. He showed how incredibly fast it could work.
Awards and Honors
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" of computer science. They won it for their "fundamental achievements in the design and analysis of algorithms and data structures."
In 1994, he was named an ACM Fellow. This honor recognized his "seminal advances in the design and analysis of data structures and algorithms."
Other awards Tarjan has received include:
- The 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 (1985).
- National Academy of Sciences Award for Initiatives in Research (1984).
- Member of the National Academy of Sciences (1987).
- Member of the National Academy of Engineering (1988).
- Member of the American Philosophical Society (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
Robert Tarjan has written many important research papers. His papers have been cited (or referenced) by other scientists over 94,000 times!
Some of his most cited papers include:
- 1972: "Depth-first search and linear graph algorithms"
- 1987: "Fibonacci heaps and their uses in improved network optimization algorithms"
- 1983: "Data structures and network algorithms"
- 1988: "A new approach to the maximum-flow problem"
See also
In Spanish: Robert Tarjan para niños
