John Hopcroft

Turing Award


To a computer scientist, studying algorithms is like a geneticist familiarizing himself with DNA or a tailor learning how to sew: fundamental. Algorithms form the basis of modern computer science, each one a well-defined sequence of steps that allows a computer to carry out calculations, solve problems, process data, among other tasks. Algorithms are just like cooking recipes that tell you how to make a dish, says John Hopcroft, the computer scientist who played a fundamental role in their development.

In the early days of computers, it was hard to compare algorithms and decide which ones were better to use. That’s because algorithms were assessed based how long they took to run, which depended on factors such as computer speed and a person’s coding skills. But Prof. Hopcroft recognized that the most important factor to consider was “asymptotic complexity,” or how a computer’s growth rate changes as it begins to work on larger, more complex problems. 

For developing a mathematical way of analyzing algorithms, Prof. Hopcroft shared the highest award in computer science, the Turing Award, with Robert E. Tarjan in 1986. Their work altered how computer science was taught, with algorithms now included as a key component in syllabuses around the world. Much of their work on algorithms has been applied to graphs, enabling applications to topics ranging from linguistics to chemistry.

Prof. Hopcroft grew up in Seattle, Washington in a family that he describes as being “poor but with a loving and secure environment.” Neither of his parents graduated from high school, but that didn’t stop them from inculcating a love for learning in their three children. “My father used to take me to see trains, or to the zoo, and just explored many things with me,” recalls Prof. Hopcroft. “That led me to be curious all my life.” 

From a young age, he became fascinated by technology — first trains, then mathematics and logic. Prof. Hopcroft knew from as young as six or seven that he would attend university because what his parents wanted “was for us children to have a better life.” And attend university he did, obtaining a Masters and Ph.D. in electrical engineering from Stanford University. How Prof. Hopcroft eventually became one of the world’s leading computer scientists was a serendipitous chain of events, sparked by his department head asking him to teach Primceton’s first ever class in the subject.

Prof. Hopcroft has been a faculty member of Cornell University since 1967, where he currently studies deep learning in artificial intelligence. “I’m excited because I think understanding how deep learning works will be a major scientific contribution,” he says. He also devotes time to improving education in other countries, with a particular focus on China. At home, he is also studying the effects of early childhood development on the future health of the U.S. society. Prof. Hopcroft is a member of the National Academy of Sciences and the National Academy of Engineering, and a fellow of the American Academy of Arts and Sciences, and the American Association for the Advancement of Science. He has just been elected a foreign member of the Chinese Academy of Science.