David Stifler Johnson (December 9, 1945 – March 8, 2016) was an American

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

specializing in

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

s and optimization. He was the head of the Algorithms and Optimization Department of

AT&T Labs AT&T Labs is the research & development division of AT&T, the telecommunications company. It employs some 1,800 people in various locations, including: Bedminster NJ; Middletown, NJ; Manhattan, NY; Warrenville, IL; Austin, TX; Dallas, TX; Atlan ...

Research from 1988 to 2013, and was a visiting professor at

Columbia University Columbia University (also known as Columbia, and officially as Columbia University in the City of New York) is a private research university in New York City. Established in 1754 as King's College on the grounds of Trinity Church in Manhatt ...

from 2014 to 2016. He was awarded the 2010 Knuth Prize. Johnson was born in 1945 in Washington, D.C. He graduated

summa cum laude Latin honors are a system of Latin phrases used in some colleges and universities to indicate the level of distinction with which an academic degree has been earned. The system is primarily used in the United States. It is also used in some Sou ...

from

Amherst College Amherst College ( ) is a private liberal arts college in Amherst, Massachusetts. Founded in 1821 as an attempt to relocate Williams College by its then-president Zephaniah Swift Moore, Amherst is the third oldest institution of higher educatio ...

in 1967, then earned his S.M. from MIT in 1968 and his Ph.D. from MIT in 1973. All three of his degrees are in

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

. He was inducted as a

Fellow of the Association for Computing Machinery 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 ...

in 1995, and as a member of the National Academy of Engineering in 2016. He was the coauthor of ''Computers and Intractability: A Guide to the Theory of NP-Completeness'' () along with

Michael Garey Michael Randolph Garey (born November 19, 1945) is a computer science researcher, and co-author (with David S. Johnson) of '' Computers and Intractability: A Guide to the Theory of NP-completeness''. He and Johnson received the 1979 Frederick W ...

. As of March 9, 2016, his publications have been cited over 96,000 times, and he has an ''h''-index of 78. Johnson died on March 8, 2016, at the age of 70.

References

External links

David S. Johnson
David S. Johnson, On-Line Encyclopedia of Integer Sequences 1945 births 2016 deaths American computer scientists Fellows of the Association for Computing Machinery Amherst College alumni Massachusetts Institute of Technology alumni Theoretical computer scientists Fellows of the Society for Industrial and Applied Mathematics Columbia University faculty Columbia School of Engineering and Applied Science faculty Knuth Prize laureates Scientists at Bell Labs Members of the United States National Academy of Engineering {{compu-scientist-stub

See also

References

External links