Skip to main content

Memorial Tributes Volume 22 (2019) / Chapter Skim
Currently Skimming:

DAVID S. JOHNSON
Pages 161-166

The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.


From page 162...
... Then he was drafted to the US Army at the height of the Vietnam War, but served as a 1st lieutenant in South Korea. An apocryphal explanation of this rather surprising deployment is that, during basic training, David humored his boredom by reading dusty Army rule books, where he learned that (1)
Read the entire page →
From page 163...
... This discovery marked the beginning of the modern era of the theory of computation -- the theory of algorithms and complexity. David Johnson's contributions to this important intellectual edifice, which has transformed the practice of all of computer science, were crucial and twofold: he was the prime exegete of the theory of computationt through his book and expository writings, and he was the first to articulate one of its most productive branches: In his 1973 PhD thesis and in a complementary 1973 paper, he laid the foundations of the study of approximation algorithms.
Read the entire page →
From page 164...
... A masterful introduction to this difficult subject for the motivated inexpert reader, it goes far beyond that. With 57,000 citations -- possibly the most-referenced work in all of computer science -- it set the style and notation for the whole area and became an indispensable research tool through its annotated catalogue of NP-complete problems.
Read the entire page →
From page 165...
... His contributions and achievements were rocognized with various honors. In 1995 he became an ACM fellow; in 1997 he received the inaugural SIGACT Distinguished Service Prize; in 2010 he was selected for the Knuth Prize, the prestigious career award for theoreticians; and he was elected to the National Academy of Engineering weeks before his death.
Read the entire page →

Key Terms

  • david johnson
  • solutions guaranteed
  • seeks efficient
  • polynomial time
  • cum laude

  • south korea
  • reading dusty
  • researcher michael
  • resist efficient
  • fiction collector

  • visiting professor
  • algorithms exploring
  • david wrote
  • graduated summa
  • david humored

  • plain food
  • army rule
  • computation theory
  • distinguished service
  • regular column

  • apocryphal explanation
  • motivated inexpert
  • untimely death
  • doctoral studies
  • summa cum

  • helped found
  • prime exegete
  • career award
  • acm fellow
  • service prize


    • This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
    More information on Chapter Skim is available.