Wednesday, May 18, 2005

Computing classics

Via a commenter at the Quantum Pontiff, I came across this course offered by Christos Papadimitriou at Berkeley. Titled 'Reading The Classics", it takes the student through a selection of the some of the best works leading upto modern theoretical computer science. Some of the key papers:
  • Euler's Konigsberg bridge paper, arguably one of the first graph theory works.
  • Turing's original paper on computability
  • Shannon's foundational work on the theory of communications. In 2005, the 100th anniversary of Einstein's annus mirabilis, I should point out that if anyone can be said to be the equivalent of Einstein, it must be Shannon. With his work on information theory and boolean logic, he created the theoretical underpinnings of both the networks and the devices that make up the Information Age we live in today.
  • Jack Edmond's work on matchings, where the notion of polynomial time as a measure of "efficiency" was first proposed (Some say it was even earlier, in a letter that Godel wrote to Von Neumann)
  • The Cook-Karp-Levin sequence of papers that laid the foundations of NP-hardness.
and many others. Most of the papers are online (and in the case of Euler's paper, in the original Latin!).

Disqus for The Geomblog