John E Hopcroft

John Hopcroft was born into a working class family on October 7, 1939 in Seattle Washington. His father was a British veteran of the First World War who moved to Canada because he was unable to find employment in Britain. He eventually worked his way to the west coast and finally to Seattle, where he met and married John’s mother and worked as a janitor.

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.

He claims that because of the lack of family experience with higher education, it never occurred to him to look at other than the local Seattle University. He graduated with a BS in Electrical Engineering in 1961.

He was a fine student and was quickly admitted to graduate studies at Stanford University, where he received a MS in 1962 and a PhD in 1964, both in 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 [1].  This volume and its many translations educated an entire generation of computer scientists. Its successor [3] is still in use today.

John’s first computer science research efforts were in an area that became known as formal language theory. Linguists had developed formal grammars for the study of human languages, and similar tools could be used for the developing high level programming languages. The earliest compilers had not been based on a theoretical foundation like that; they were simply a collection of ad-hoc routines that analyzed the statements in a high level language and created the equivalent set of instructions in computer machine code. This process sufficed for the earliest compliers but quickly became unworkable as languages increased in complexity. John made fundamental advances in formal grammars before turning his attention to the study of algorithms.

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).

Hopcroft’s work on graph algorithms was not just theoretical analysis, it also included synthesis. He explored efficient structures for storing data in a computer, and created efficient algorithms for solving the problems they could represent. This work, new and exciting at the time, is now part of the standard computer science curriculum.

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 [1] and on the design and analysis of algorithms [2] became the standards for a generation of computer scientists.

His current work, which again uses graph models, explores ways to track social networks and build the search engines of the future.

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.

Throughout his career, Hopcroft has helped the field by serving on national and international committees. The respect for his views and his work are evident from the many honors he has received.