Top 150 computer science events to be decided once and for all

Today I break Shtetl-Optimized‘s long radio silence with a relatively-exciting announcement: you remember my timeline of computer science history?  Well, MIT students Jason Zhu and Ammar Ammar have now kindly created a website where you can vote on each of the entries, as well as new entries suggested by commenters.  It’s pretty simple: you just register (by entering an email address, username, and password), then upvote each entry you like and downvote each entry you dislike (you can also abstain on any entry).

The voting site arrives just in time for the MIT symposium “Computation and the Transformation of Practically Everything”, which is happening today and tomorrow.

For reference, here are the 17 new contenders added by popular demand:

150BC Chinese text describes Gaussian elimination
499 Indian mathematician Aryabhata describes the “kuttaka” algorithm for solving Diophantine equations
1206 al-Jazari builds elaborate water clocks and musical automata
1801 The Jacquard loom uses punched cards to control textile manufacturing
1951 Wilkes, Wheeler, and Gill describe the concept of closed subroutines
1956 Stephen Kleene invents regular expressions
1962 The Atlas computer begins operation in Manchester
1962 Robert Gallager introduces low-density parity check codes
1968 First deployed packet-switching network
1969 Strassen’s algorithm for fast matrix multiplication
1969 Stephen Wiesner conceives of quantum money and multiplexing
1971 Vapnik and Chervonenkis introduce VC dimension
1982 PostScript
1992 The PCP Theorem
1999 SETI@home
2006 DaVinci surgical robot performs the first unaided operation
2007 Checkers solved

Update: A new feature has been added that lets you rank four randomly-selected entries—click “Done” on the bottom of the page to access it.

Update: You can now undo a vote by clicking twice on the same arrow.

27 Responses to “Top 150 computer science events to be decided once and for all”

  1. Ross Snider Says:

    As a computer scientist I’m offended the interface for the sorting of importance of events doesn’t depend on the swapping of two elements! Really, there are at least 150 elements in the list. You ought to have exposed the root level of Mergesort, asking each person to make only simple comparisons. As it stands you’re asking me to implement Bubblesort. My time is more precious.

    Also, there appears to be a bug? “Euclid’s Elements” shows up in my list to sort by importance at least three times. There are several others behaving the same way. (Maybe clicking on the “accept checkmark” multiple times adds a topic to the sort by importance list multiple times?)

    Otherwise, I think its great you’ve created this collaborative tool.

  2. Scott Says:

    Ross: Not only did we consider a comparison-based voting system, but Ammar and his adviser have a prototype of such a system that we’re planning to test a bit later (as an alternative to the current up-or-down system). However, comparison-based voting has drawbacks of its own for this application: I don’t WANT to have to decide whether MS Office was more or less important than the Time Hierarchy Theorem. Instead, I just want to express my approval or disapproval for the subset of entries I care about.

  3. Scott Says:

    As for the bug: sorry, we’ll look into it!

  4. Shehab Says:

    Just voted!

  5. Scott Says:

    OK, Ammar tells me the bug is fixed now.

  6. Vlad Levin Says:

    some additional features i wouldn’t mind seeing: mark an entry as having a bug (error, incomplete, etc); mark entries as duplicates/closely enough related to be considered for merging (i can envisage having a main entry that will be published that is most representative of a given achievement and additional entries that are closely related which perhaps would show up as footnotes or only in the electronic version of the list).

  7. Sniffnoy Says:

    A problem: There’s no way to undo a vote, except by changing it to the other! I can change from down to up but not from down to neutral.

  8. Scott Says:

    Sniffnoy: Thanks for pointing that out! I’ve asked Jason and Ammar to fix it.

  9. Andy McKenzie Says:

    Hey Scott, love the site. One issue: once you vote something up or down there’s no way to change your vote back to neutral. Maybe you could click on your up vote and have it reset?

  10. Yatima Says:

    Hmmm…..

    It’s “Wiener”, not “Weiner”.

    The site definitely shows that being knowledgeable in Computer Science does not a good website developer make.

  11. Robert Says:

    For starters, the word “bug” wasn’t coined in 1947. The moth trapped in a relay was noted because the word bug has been used in engineering since at least the 19th century, and may even go back to the middle ages.

    No Boyer-Moorse string search algorithm?

    You list the Pentium FDIV bug, but not on followup work by Intel and AMD in using formal methods to verify their processors.

    You don’t important dates for the introduction of important software for formal method, such as ACL2, Coq, Isabelle, Agda, NuPrl (1979), LEGO, etc. Not even mention of the first rudimentary theorem provers.

    You don’t list Martin-Löf’s work on constructive set theory, which is (by some) considered the most important book in logic written in the past 50 years, and is the foundation for emerging dependently-typed programming languages (Agda, Epigram, etc.)

    Haskell is important for being the first “pure” functional language. Monads are not mentioned at all, which are very important. Likewise, no mention of category theory, also very important for theoretical computer science.

    Nothing about the invention of Prolog or the WAM compiler.

    No mention of Gentzen and the invention of natural deduction/sequent calculi, which are so important for logic programming and type inference?

    No mention of intuitionistic logic at all? (Brouwer, or Heyting’s formalisation, or Komolgorov semantics)?!!!

    No mention of Girard and Linear Logic, etc.? Not only for substructural logics, but for resource analysis of computer programs much later.

    No mention of the first fuzzy logics (Łukasiewicz in early 20th century, and later Zadeh in 60s)?

    The invention of relational semantics for logics? (Beth, Hintikka, and Kripke) in the 1950s and 60s?

    No mention of Leibniz’s work in calculus, which some consider more important than Newton.

    No mention of Plotkin’s work connecting operational and denotational semantics?

    No mention of Java programming language. (Controversial, but some might consider it to be an important milestone.) What about Pascal programming language?

    Markov chains?

    Beysian Inference?

    No mention of Church’s introduction of the Lambda calculus?!?

    There are so many, too many, *important* events in the history of computer science that are left out of this list.

  12. WantedToHearScottAndErikButCantAffordIt Says:

    It’s a shame that MIT charges for the two-day event of talks. I wanted to hear Scott and Erik (Demaine) speak at the event, but unfortunately, it’s $25. I simply can’t afford it! Sorry MIT, but you’re already too rich for this. Shame.

  13. Scott Says:

    WantedToHearScottAndErikButCantAffordIt: As someone pointed out to me, you can watch all the talks on streaming video, for free, starting tomorrow. (On the other hand, without coughing up $25 you can’t enjoy the delicious boxed lunches.)

  14. Ross Snider Says:

    There’s nothing like doing a lot of hard work and releasing a tool to the world only to receive negative feedback.

    I didn’t mean to be harsh on your student developers. I think the site is a great idea. I’m voting now.

  15. Yatima Says:

    “There’s nothing like doing a lot of hard work and releasing a tool to the world only to receive negative feedback.”

    You took the redpill. Welcome to the Terror of the Real.

  16. Name Says:

    There’s one thing I would have certainly put forward but it’s not on your list. I can understand why it’s not, but that’s a pity. Maybe you should include a mechanism so that outsiders can add some events they think should be voted for, such as the appearance of this paper:

    http://arxiv.org/abs/1011.3245

    ;-)

  17. Vladimir Ufimtsev Says:

    Scott,

    How about Len Adleman’s demonstration in 1994 of how DNA can be used for computation? Sure it was only for DNA but the idea of using molecules or biological entities such as bacteria or viruses for computation seems to be worthy of mention (even if it’s not specifically Adleman’s demonstration).

  18. Scott Says:

    Vladimir: I didn’t feel DNA computing had led to enough either practically or theoretically. But maybe (e.g.) something about biological self-assembly should’ve been there…

  19. Raoul Ohio Says:

    Allow me a brief interruption. For the many SO participants who enjoy a good chuckle when another of Noam Chomsky’s dingbat theories gets trashed, check out:

    http://www.sciencedaily.com/releases/2011/04/110414065107.htm

  20. asdf Says:

    Scott, it’s a bit late, but re “Building on earlier breakthroughs by Polish mathematician Marian Rejewski, …” I wish you could add (at minimum) “and colleagues”, referring to Henryk Zygalski and Jerzy Różycki. There are biographies of them in Wikipedia, and nobody remembers the other two guys. Jerzy Różycki died in 1942 on board a ship that sunk under unclear circumstances, while Rejewski and Zygalski went on to live long lives.

  21. asdf Says:

    I keep clicking the blue links above the timeline entries, expecting to reach informative pages about the topics, oh well. Maybe some could be linked to wikipedia?

  22. wolfgang Says:

    >> DaVinci surgical robot performs the first unaided operation

    the wording of this entry is quite misleading, since at all times the surgeon is in full control of the robot.

  23. LookingForVideos Says:

    You said you can watch the Symposium videos online? Anyone have a link? Can’t find it.

  24. asdf Says:

    Norbert Wiener’s famous work on cybernetics is a book, not a paper.

    Norbert Wiener (1948), Cybernetics or Control and Communication in the Animal and the Machine, (Hermann & Cie Editeurs, Paris, The Technology Press, Cambridge, Mass., John Wiley & Sons Inc., New York, 1948).

  25. Jim Cliborn Says:

    @22 I found this “Some argue, however, that perhaps the greatest leap took place in Rome in 2006, when a team of
    physicians in Boston, MA, monitored a robotic surgical
    system performing an undisclosed heart procedure
    unaided. The procedure took approximately 50
    minutes and was performed solely by the robot.”

    Ref: http://www.premierinc.com/about/news/inthenews/fundamentals-of-robotic-surgical-systems.pdf

    Barrett Franklin
    “Robotic Surgical Systems”
    Biomedical Instrumentation & Technology, Nov./Dec. 2006, p.461

  26. hardware nut Says:

    What about cisc vs risc, or even vliw and epic. What about developments concerning the memory wall and other design developments (like cache hierachies) to minimize practical bottlenecks in computing.

  27. Anonymous Says:

    What about Jack Edmond’s 1965 paper, “Paths, Trees, and Flowers”, which made the distinction between “finite” and “algebraic” programs, and led the way to the P, NP, and co-NP categorization?

Leave a Reply