John Edward Hopcroft (born October 7, 1939) is an American theoretical

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

. His textbooks on

theory of computation In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., a ...

(also known as the

Cinderella book ''Introduction to Automata Theory, Languages, and Computation'' is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation. Rajeev Motwani contributed to later editions beg ...

) and

data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...

s are regarded as standards in their fields. He is the IBM Professor of Engineering and Applied Mathematics in Computer Science at

Cornell University Cornell University is a private statutory land-grant research university based in Ithaca, New York. It is a member of the Ivy League. Founded in 1865 by Ezra Cornell and Andrew Dickson White, Cornell was founded with the intention to teach an ...

, Co-Director of the Center on Frontiers of Computing Studies at

Peking University Peking University (PKU; ) is a public research university in Beijing, China. The university is funded by the Ministry of Education. Peking University was established as the Imperial University of Peking in 1898 when it received its royal charter ...

, and the Director of the John Hopcroft Center for Computer Science at

Shanghai Jiao Tong University Shanghai Jiao Tong University (SJTU; ) is a public research university in Shanghai, China. The university is funded by the Ministry of Education of China. The university was established on April 8, 1896 as Nanyang Public School (南洋� ...

Education

He received his

bachelor's degree A bachelor's degree (from Middle Latin ''baccalaureus'') or baccalaureate (from Modern Latin ''baccalaureatus'') is an undergraduate academic degree awarded by colleges and universities upon completion of a course of study lasting three to six ...

from

Seattle University Seattle University (SeattleU) is a private Jesuit university in Seattle, Washington. Seattle University is the largest independent university in the Northwestern United States, with over 7,500 students enrolled in undergraduate and graduate prog ...

in 1961. He received his

master's degree A master's degree (from Latin ) is an academic degree awarded by universities or colleges upon completion of a course of study demonstrating mastery or a high-order overview of a specific field of study or area of professional practice.

and

Ph.D. A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is ...

from

Stanford University Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is consider ...

in 1962 and 1964, respectively. He worked for three years at

Princeton University Princeton University is a private university, private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial Colleges, fourth-oldest ins ...

and since then has been at

. Hopcroft is the grandson of Jacob Nist, founder of the Seattle-Tacoma Box Company.

Career

In addition to his research work, he is well known for his books on

algorithms In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing c ...

and

formal languages In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (formal languages), alphabet and are well-formedness, well-formed ...

coauthored with

Jeffrey Ullman Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the dr ...

and

Alfred Aho Alfred Vaino Aho (born August 9, 1941) is a Canadian computer scientist best known for his work on programming languages, compilers, and related algorithms, and his textbooks on the art and science of computer programming. Aho was elected into ...

, regarded as classic texts in the field. In 1986 he received the

Turing Award The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in compu ...

(jointly with

Robert Tarjan Robert Endre Tarjan (born April 30, 1948) is an American computer scientist and mathematician. He is the discoverer of several graph algorithms, including Tarjan's off-line lowest common ancestors algorithm, and co-inventor of both splay trees a ...

) "for fundamental achievements in the design and analysis of algorithms and data structures." Along with his work with Tarjan on

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

s he is also known for the

Hopcroft–Karp algorithm In computer science, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output – a set of ...

for finding matchings in

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

s. In 1994 he was inducted as a

Fellow A fellow is a concept whose exact meaning depends on context. In learned or professional societies, it refers to a privileged member who is specially elected in recognition of their work and achievements. Within the context of higher education ...

of the

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional member ...

. In 2005 he received the Harry H. Goode Memorial Award "for fundamental contributions to the study of algorithms and their applications in information processing." In 2008 he received the Karl V. Karlstrom Outstanding Educator Award "for his vision of and impact on computer science, including co-authoring field-defining texts on theory and algorithms, which continue to influence students 40 years later, advising PhD students who themselves are now contributing greatly to computer science, and providing influential leadership in computer science research and education at the national and international level." Hopcroft was elected a member of the

National Academy of Engineering The National Academy of Engineering (NAE) is an American nonprofit, non-governmental organization. The National Academy of Engineering is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy ...

in 1989 for fundamental contributions to computer algorithms and for authorship of outstanding computer science textbooks. In 1992, Hopcroft was nominated to the

National Science Board The National Science Board (NSB) of the United States establishes the policies of the National Science Foundation (NSF) within the framework of applicable national policies set forth by the President and the Congress. The NSB also serves as an ind ...

George H. W. Bush George Herbert Walker BushSince around 2000, he has been usually called George H. W. Bush, Bush Senior, Bush 41 or Bush the Elder to distinguish him from his eldest son, George W. Bush, who served as the 43rd president from 2001 to 2009; pr ...

. In 2005, he was awarded an honorary doctorate by the University of Sydney, in Sydney, Australia. In 2009, he received an

honorary doctorate An honorary degree is an academic degree for which a university (or other degree-awarding institution) has waived all of the usual requirements. It is also known by the Latin phrases ''honoris causa'' ("for the sake of the honour") or ''ad hon ...

from

Saint Petersburg State University of Information Technologies, Mechanics and Optics ITMO University (russian: Университет ИТМО) is a state-supported university in Saint Petersburg and is one of Russia's National Research Universities. ITMO University is one of 15 Russian universities that were selected to particip ...

. In 2017,

launched a John Hopcroft Center for Computer Science. In 2020 the

Chinese University of Hong Kong, Shenzhen The Chinese University of Hong Kong, Shenzhen (CUHK-SZ) is a campus of the public Chinese University of Hong Kong in Shenzhen, Guangdong. It is a joint venture between Shenzhen University and the Chinese University of Hong Kong. CUHK-Shenzhen was ...

opened a Hopcroft Institute for Advanced Information Sciences and designated him as an Einstein professor. Hopcroft is also the co-recipient (with

) of the 2010

IEEE John von Neumann Medal The IEEE John von Neumann Medal was established by the IEEE Board of Directors in 1990 and may be presented annually "for outstanding achievements in computer-related science and technology." The achievements may be theoretical, technological, or ...

“for laying the foundations for the fields of automata and language theory and many seminal contributions to theoretical computer science.”

Awards

* 1986.

* 1989.

Member * 1994. ACM Fellow * 2005. Harry H. Goode Memorial Award * 2008. Karl Karlstrom Outstanding Educator Award * 2010.

* 2016.

Friendship Award (China) The Chinese Government's Friendship Award () is the People's Republic of China's highest award for "foreign experts who have made outstanding contributions to the country's economic and social progress". The award was first established in 1950s, ...

Selected publications

; Books * 2017.
Foundations of Data Science
'. (with

Avrim Blum Avrim Blum (born 27 May 1966) is a computer scientist. In 2007, he was made a List of Fellows of the Association for Computing Machinery, Fellow of the Association for Computing Machinery "for contributions to learning theory and algorithms." Blu ...

and

Ravindran Kannan Ravindran Kannan ( ta, ரவீந்திரன் கண்ணன்; born 12 March 1953, Madras) is a Principal Researcher at Microsoft Research India, where he leads the algorithms research group. He is also the first adjunct faculty of ...

) * 2001. J.E. Hopcroft, Rajeev Motwani,

Jeffrey D. Ullman Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the ...

, ''

Introduction to Automata Theory, Languages, and Computation ''Introduction to Automata Theory, Languages, and Computation'' is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation. Rajeev Motwani contributed to later editions begi ...

'' Second Edition. Addison-Wesley. * 1983. Alfred V. Aho, J.E. Hopcroft, Jeffrey D. Ullman, ''Data Structures and Algorithms'', Addison-Wesley Series in Computer Science and Information Processing. * 1974. Alfred V. Aho, J.E. Hopcroft, Jeffrey D. Ullman, ''The Design and Analysis of Computer Algorithms'', Addison-Wesley Series in Computer Science and Information Processing. * 1969. '' Formal Languages and Their Relation to Automata''. (with Jeffrey D. Ullman), Addison-Wesley, Reading MA.

References

External links

John E. Hopcroft at Cornell University
{{DEFAULTSORT:Hopcroft, John American computer scientists 1939 births Living people Fellows of the Association for Computing Machinery Fellows of the Society for Industrial and Applied Mathematics Members of the United States National Academy of Engineering Members of the United States National Academy of Sciences Turing Award laureates Cornell University faculty Stanford University alumni Seattle University alumni 20th-century American engineers 21st-century American engineers 20th-century American scientists 21st-century American scientists Computer science educators American textbook writers American electrical engineers