John grew up in Seattle and attended the local schools. Neither of his parents were high school graduates, but they instilled in him a love of learning and worked hard to ensure that he had the chance to obtain more education than either of them had. At an early age John was fascinated by technology – trains at first, and later mathematics and logic, particularly those aspects relating to electrical engineering.

John’s first academic job was as an Assistant Professor of Electrical Engineering at Princeton. He became a computer scientist almost by accident, when his department head asked him to teach a class in computing science.

Since he had no experience in the subject, he had to ask what subjects should be included. The department head recommended a few papers, and John managed to create and teach this first course to six bright students who in turn motivated him. He taught that class for several years, but he says that first year was the most enjoyable because he and his few students were feeling their way into unfamiliar territory together.

One of those first students was Jeff Ullman, who would become a major collaborator in his work. Jeff left Princeton to work at Bell Laboratories and teach an evening course at Columbia University. This was the era when there were few computer science texts, particularly for the theoretical aspects of the subject. Hopcroft and Ullman took John’s course notes and expanded them into one of the earliest and most influential books on the subject.  This volume and its many translations educated an entire generation of computer scientists. Its successor is still in use today.

In the early days of computers, algorithms tended to be compared based on total running time, which depends on the speed of the computer, the programming efficiency, the constant overhead of the algorithm, and the growth rate of the running time as the input gets larger. John recognized that as computers became faster and worked on larger problems, the most important part to understand was the last: the growth rate of the running time. His focus on this “asymptotic complexity” set the direction for the new field of analysis of algorithms.

Much of this work dealt with the algorithms used to manipulate graphs, which are made from a set of points (vertices) connected by lines (edges). While this may appear to be a very academic and abstract subject, many practical problems can be described using graphs. Thus any improvements in the general algorithms used to manipulate graphs can provide practical improvements to real life problems. Such problems span the range from linguistics (for grammar and syntactic analysis), to chemistry (for modelling of atoms and molecules to compute their properties), to network analysis (for determining the flow of traffic in the World Wide Web or in highways).

His work on formal languages and the analysis of algorithms has made John Hopcroft one of the handful of pioneering computer scientists who put the discipline on a firm theoretical foundation. His co-authored texts on formal languages and their relation to automata  and on the design and analysis of algorithms  became the standards for a generation of computer scientists.

John is not only a respected researcher, but also an inspiring teacher. Each year the top 20 graduates at Cornell are asked to name the professor that had the most influence on their education. John has been chosen twice, a record of which he is justly proud.

He believes that students should be required to take fewer specialist courses. They should be allowed acquire a broad education and have more free time to learn things on their own. He admits that his success in changing university curricula requirements has been limited, but he’s still trying.

Hopcroft has been an influential and inspiring PhD advisor to at least 34 students since 1967. His advisees learned how to do research from him, but they also absorbed his sense of discrimination, his standard of excellence, and his commitment to community service. Many of them now serve in influential positions in academia and industry. Among his PhD students are the president of an Israeli university, a MacArthur Fellow, a vice president of a computing research firm, and many chairs of academic departments.

Papers

Videos