Friday, December 23, 2016

Classics of Computer Science

While waiting for the new term to begin, I have drafted a proposal of a new course I hope to teach. I borrowed shamelessly from courses taught elsewhere and from the advice of my colleagues. Below I paste a draft syllabus, which links off to a longer reading list. I would be grateful for advice on two points. First, the class by class selection of papers--do I have the right ones, given that each class can cover only a few? And second, what pedagogical style might work for a course of this kind? I have some ideas, but would like to hear some fresh ones. I don't want to limit enrollment (except by stating some prerequisite--basically, junior or senior standing, and having taken at least one sophomore-level CS course), but I also don't want (and surely could not find) an army of qualified teaching assistants to read weekly papers. I would guess I will get 50-150 students, though I might decide to hold that number down naturally by teaching in the disused 8:30-10am time slot.

Thanks for your advice!

-------------------------------

Classics of Computer Science – draft course syllabus

An Engineer is said to be a man who knows a great deal about a very little, and who goes around knowing more and more, about less and less, until finally, he practically knows everything about nothing; whereas, a Salesman, on the other hand, is a man who knows a very little about a great deal, and keeps on knowing less and less about more and more until finally he knows practically nothing, about everything. – from a newspaper in the 1930s

Well those drifters days are past me now
I've got so much more to think about
Deadlines and commitments
What to leave in, what to leave out
-        Bob Seeger, Against the wind

Argument
This course is intended as a synthesizing experience for juniors and seniors in computer science, a way for them to see the field as a whole, not through a survey, but by reliving the experience of its creation.

Our overarching goal is to create a unified view of the field of computer science for students who already know something about it. Even though the field is becoming splintered, a talented undergraduate can in four years learn something about all the major areas, and about how they connect together. Students can, and should, understand the development of the field from its origins, to understand what Boole, Babbage, and Turing were trying to do, and to see, in retrospect, how later scientific developments evolved from these roots. The structure of our undergraduate curriculum balances depth and breadth—we want students to be able to drill down on special areas of interest, and to develop some in-depth expertise, while not concentrating their studies exclusively on one subfield. But the balance is increasingly uneasy. Reading across time has the merit of helping students understand that the fragmentation of CS into specialty areas was not a divine creation—that indeed, speciation is the result of a still ongoing process of invention and discovery.

Because the field is young, many of the seminal papers are as readable today as when they were written. We will, each week, read and discuss several related papers. Some true classics we will read in full, because they are models of clarity as well as creativity, while other papers will be read only in part, their technical details having been superseded or rendered obsolete by later developments.

I intend this to be a 100-level course with a “0” or “9” penultimate digit so that it will count for concentration in Computer Science but will not be usable to fulfill the breadth requirement.

Learning objectives:
·      To identify the major subfields of computer science, their intellectual family tree, and the major figures and works of their birth and infancy.

·      To be able to place current computer science research in the context of its intellectual lineage.

·      To be able to present to an audience of educated but non-specialist computer scientists some of the major ideas of computer science in a way that is succinct and easy to understand.

·      To be able to critique constructively similar presentations by others.

Syllabus
There are 25 ninety-minute classes in the term for courses meeting twice a week. The syllabus below is a first cut at organizing the classes. One of the challenges will be to edit the list down, or to limit the number of pages from many of the papers without gutting the technical content. These papers are drawn from a master list which is publicly viewable and includes links (some requiring a Harvard login).

The syllabus combines field coherence and chronology by ordering topics according to the date of the earliest paper in that topic’s reading list. So while students will jump from topic to topic in an apparently chaotic way, every week they will begin their reading with a paper written only shortly after the first paper they read the previous week.

I am using the term “Classics,” but that is really too grandiose. Some of the papers are just the first to do something, and thus report astonishingly important discoveries, but may not be expository models for others to follow. Some are arguably wrong, or did as much to send the field off in a wrong direction as to drive it forward. It is not a bad thing for students of computer science to discuss hype as a cautionary tale against exaggerated claims they will surely hear the future.

1.     Overview and responsibilities
2.     Infrastructure
a.     Leibniz 1677
b.     Boole 1853
c.     Moore 1965
3.     Origins
a.     Menabrea & Lovelace 1842
b.     Hilbert 1900
c.     Turing 1936
4.     Architecture
a.     Aiken 1938
b.     Burks, Goldstine, von Neumann 1946
c.     Wilkes 1951
d.     Kilburn 1962
5.     Information
a.     Shannon 1938
b.     Shannon 1948
c.     Hamming 1950
6.     Learning
a.     McCulloch and Pitts 1943
b.     Rosenblatt 1958
c.     Valiant 1985
d.     Rumelhart et al. 1986
7.     Computers for people
a.     Bush 1945
b.     Licklider 1960
c.     Englebart 1962
d.     Englebart 1968
e.     McCarthy 1970
f.      Kay 1972
g.     Thacker et al 1979
8.     Computers and thinking
a.     Turing 1950
b.     Shannon 1950
c.     Shannon 1953
9.     Formal models
a.     Kleene 1951
b.     Chomsky 1956
c.     Rabin and Scott 1959
d.     Knuth 1965
e.     Shieber 1985
10.  Software as engineering
a.     Hopper 1952
b.     Brooks 1975
c.     Leveson 1993
11.  Artificial intelligence
a.     McCarthy, Minsky, Rochester, Shannon 1955
b.     Weizenbaum 1966
c.     Block 1981
12.  Complexity before NP
a.     Godel 1956
b.     Hartmanis and Stearns 1963
c.     Blum 1967
13.  Programming languages
a.     Backus 1959
b.     Naur 1963
c.     DoD 1975
d.     Aho et al. 1978
14.  System design
a.     Corbato et al. 1962
b.     Dijkstra 1967
c.     Ritchie and Thompson 1974
d.     Saltzer et al 1983
15.  Algorithms
a.     Gale and Shapley 1962
b.     Hoare 1962
c.     Edmonds 1965
d.     Strassen 1969
e.     Blum et al. 1973
f.      Carter and Wegman 1979
16.  Graphics and interaction
a.     Sutherland 1963
b.     Sutherland 1965
c.     Myer and Sutherland 1968
17.  Networks
a.     Baran 1964
b.     Cerf and Kahn 1974
c.     Metcalfe and Boggs 1976
d.     Clark 1988
18.  Control abstractions
a.     Dijkstra 1968
b.     Gray et al. 1975
c.     Lampson 1978
d.     Birrell 1989
19.  Programs as formalisms I
a.     Hoare 1969
b.     Floyd 1969
c.     Scott 1970
20.  Complexity after NP
a.     Cook 1971
b.     Karp 1972
c.     Levin 1973
d.     Goldwasser, Micali, Rackoff 1985
21.  Data organization and retrieval
a.     Codd 1972
b.     Spärck Jones 1972
c.     Bayer and McCreight 1972
d.     Salton et al 1975
22.  Graphical rendering
a.     Catmull 1974
b.     Newell and Blinn 1979
c.     Witted 1980
d.     Kajiya 1986
23.  Security and cryptography
a.     Diffie & Hellman 1976
b.     Rivest, Shamir, Adleman 1978
c.     Goldwasser and Micali 1984
d.     Thompson 1984
e.     Anderson 1993
24.  Programs as formalisms II
a.     Milner 1977
b.     Liskov et al. 1977
c.     Demillo, Lipton, Perlis 1979
d.     Naur 1982
25.  The web
a.     Berners-Lee 1989
b.     Berners-Lee et al. 1992
c.     Page et al. 1998

Reading period assignment: Meaningful papers about CS that are not CS papers
a.     Sutherland 1980
b.     Gefter 2016


19 comments:

  1. I would suggest Tony Hoare's Turing award acceptance speech in 1977 when he pointed out that stripping out array bounds checking was going to lead to tears. As it has, see 'Smashing the stack for fun and profit' in Phrac, another classic.

    ReplyDelete
    Replies
    1. Thanks! I have tried to be careful about Turing Award lectures -- just reading them all would be a good course, but a different kind of course than what I intend. But you are right -- Hoare's fits right in and puts some of the other PL papers in context.

      Delete
  2. I miss the papers about the interactions between CS and society. Not my area, but some mention of things like crypto vs NSA (where the good guys had a temporary victory), Lessig's clear expositions on how computer code can be an extrajudicial law, or databases and privacy (here you could even have papers -- perhaps Dwork's ICALP one.)

    ReplyDelete
  3. I do like the idea of including how computers have changed our experience of basic interactions in life. Here's a positive example: My ex wife and I are divorced and my children spend much of their time in San Antonio, while I live in Dallas. But the times they are not here, that time is not lost to me, in part because we have this wonderful app called Google Hangouts. So instead of merely hearing a voice over a telephone line, we can see facial expressions and pick up on non-verbal cues which are part of "full" communication. Technology has shrunk the physical distance for us, which has resulted in an improved relationship with my family.

    I know it is tempting to focus on the big headline grabbing issues such as privacy, but there is something truly beautiful about how the ordinary is made better because of these "everyday heroes" of computer science.

    ReplyDelete
  4. I will admit to being really excited and a little worried about this. Excited because I think reading this stuff would be great fun and give a really great springboard to new connections and new ideas. I also think it's really important to show how great ideas come from actual people -- the ideas don't just drift down full formed from some sort of heavenly oracle. Making that connection helps inspire students to have their own great ideas.

    Which leads me to my worry -- I don't recognize every name on this list, but the ones I do are overwhelmingly male. If you're sending the message that people create technology, it's easy for someone to draw the conclusion that only male people create important technology.

    I'm definitely not saying that your selection process was biased. The problem is the whole generation pipeline (who studied CS, who was in a position to think big thoughts, who had the respect to have their ideas listened to) was biased for decades (and, honestly, still is). If you do some digging beyond the "usual suspects", you might find other important ideas that come from a more diverse set of people.

    And, finally, a suggestion that is not at all helpful in increasing diversity. Lorensen and Cline's Marching Cubes paper (SIGGRAPH '86ish) is the foundation to a bunch of stuff in graphics and visualization. It's actually been used way more for real work than the ray-tracing approaches. The ray tracing stuff belongs, but this does too.

    -- Penny

    ReplyDelete
    Replies
    1. Penny,
      Thanks so much! If you go to the long list (link in the Syllabus section above, first para), you'll see that I included a "Female Au?" column. An old timer was able to confirm for me that one of the authors of the original Fortran paper was a woman, and told me a little bit about her. I didn't consciously tip for women when I selected from that pool, however, so the papers with a woman author that I selected are by Lovelace, Hopper, Backus et al [including Lois Haibt], Leveson, Goldwasser, Sparck Jones, and Liskov. The one who is most obviously missing is Fran Allen, and I'd welcome a suggestion of a "classic" of hers -- I don't find her papers (or the Allen-Cocke papers) all that readable, though they were certainly important. In the long list are also papers by Dorothy Denning, Sally Floyd, Cynthia Dwork, and Deborah Estrin -- should any of their papers be promoted, and if so in place of what? Susan Graham and Sheila Greibach didn't make the long list, can anyone suggest papers of theirs that belong there? What to leave in, what to leave out!

      Delete
  5. Great list- LONG list! a few comments
    1) I can't tell if the list is biased-towards theory or if
    that really is a major part of CS or if I have a too-expansive view of `theory'

    2) Same with women- is your list biased or is the field biased and what to do if it is.

    3) Many Turing Award lectures are readable to non-cs people. I think Karps and Hoare's are.

    4) No real mention of Facebook, Google, or Amazon.

    5) You might include this somehwere that I missed:
    Wikileaks, Snowden.

    6) There is a lot of great stuff about Societies and computers in a book called `blown to bits'- if you want I
    can send you a review I wrote so you can judge. (There are also other books along these lines- computers/society/law)

    7) Having just advised you to add more to your list I'll say the list is already too long. but it depends on how much time you spend on each one. Not sure how much time you will spend on, say, ``After NP''

    8) Theory-bias(?)- under Crypto and Security you have three papers on crypto and I think two in security. Crypto is an important but small part of security.

    9) If the list is the order you would present things in I would recommend changing it to put topics that are similar (e.g., Theory before/after NP, and algorithms) adjacent so the students can keep their train of thought.

    10) Here is hard call- you left out Cantor whose diag argument has been called by Soare ``the first result in computability theory'' But alas, I am again saying

    Your list is too long

    Here is what you an add

    11) Okay, so what to cut or abbreviate: As I said above,
    merging the theory topics together, merting other topics like PL, might help. Any topic that has \ge 4 items, get rid of some of them since after 4 we get the point.

    12) I don't see Machine Learning, Deep Blue, Alpha Go.

    13) Gee- could you make it a year-long course (I doubt that)

    14) Gee- could I take it? While the above are objections the course does look great

    ReplyDelete
    Replies
    1. Bill,
      A few quick thoughts.
      1) In the old days people just built systems. They didn't write papers. Papers might be abstracted from programs, but in the beginning CS was an act of abstraction, not imagination. (Of course Turing 1936 was an act of imagination, because that was before there was anything from which to abstract.) There is probably more to say about this, but it probably has to do with the dual nature of CS as science and engineering.
      2) See my response to Penny's comment above. I would love to know what I am missing.
      3) Yes, but I tried to avoid Turing talks because to the extent they are classics, they are ex post facto classics, important as retrospectives, and that is not what I want the course to be. I did include Thompson 1984, because it's both readable and original, not a retrospective.
      4) I have Page et. al 1998. Not sure what the comparable classics would be about FB or Amazon.
      5) Again, are Wikileaks and Snowden Classics of CS? What papers? I am not trying to include everything important that CS has enabled.
      6) See #5. I used to teach a course about that stuff and would love to do so again, but that is a different course.
      7) Each block is one 90 minute class. This will work only if I essentially pre-highlight papers so that, while some will be read in full, others will be read only for a few pages or even a few paragraphs.
      8) I would welcome suggestions of classic papers on security.
      9) I don't want them to have a train of thought. I want them to experience the field as it grew. So the gross organization (by date of earliest paper cited for the block) gives a sense of chronological progress for the field as a whole, while, the sequence within a single class speaks to progress in development of a subfield. Every so often you pick up a topic a few weeks later, understanding it as an offshoot of something seen earlier on, but not the previous week.
      10) Indeed I still do Cantor in the first week of CS121. Never thought of reading the original paper. Thanks for the suggestion.
      11) I like my ordering principle, but you are right that 4 should be an upper limit for any class, even with highly selective page choices. So what would you leave out in the blocks that have >4 papers? Cf. Bob Seeger.
      12) Well, there is some ML in #6, but I would be glad for suggestions of what to add or change. Not sure about the classics (or the importance even) in massive game searching but would be glad for suggestions.
      13) I am teaching only one term next year. More importantly, I think it would be less attractive as a full year course.
      14) One interesting question is whether there is some way I can offer this online to a larger audience, as I have, using very different pedagogical styles, with CS20 and CS121.

      Delete
    2. Our back and fourth raises a different question:
      If the course in on Classic Paper of CS then it may miss some important and interesting stuff (e.g., Amazon) that does not fit into the paper-motif of academia.

      I dont' have a recommendation here, but think its interesting that papers don't quite capture everything. In Math I think papers do, in Physics I think papers do. Engineering- not sure.

      bill g.

      Delete
  6. in algorithms, in my opinion, DFT is MUCH more impactful than at least quicksort... QS is more a media hype... DFT is much more concrete and versatile... also transformation is among most important and basic problem solving methodology.. I think LP is also great and original. Dynamic programming is also a breakthrough in computational thinking with very wide impact factor.. In security, Yao millionaire problem, and MPC are truly original and remarkable ideas..

    ReplyDelete
    Replies
    1. Thanks. I don't know these areas as well as I should -- would love specific paper suggestions. Remember, this is not a survey course, and just because an idea has proved to be important, that does not mean that the original paper on it is a classic. (A bit on this vein, it is striking that nobody, including me, has thought it important to include (either) Church 1936, while it would be unthinkable to omit Turing 1936!)

      Delete
  7. This comment has been removed by a blog administrator.

    ReplyDelete
  8. This comment has been removed by the author.

    ReplyDelete
  9. I do not have much in the way of helpful advice, other than to say as a former teaching assistant of yours that I would have been thrilled both to take and help administer such a course. In retrospect the balance of college time I spent on problem sets vs. reading was wildly off-kilter in each of the three departments (computer science, math, economics) where I took the most courses.

    ReplyDelete
  10. This comment has been removed by a blog administrator.

    ReplyDelete
  11. This comment has been removed by a blog administrator.

    ReplyDelete
  12. Hi Professor, I am very much interested in this course, but quiet afraid about the reading list and the number of pages in some of them. I do realize that you will be highlighting some sections, pages, paras as needed. But what is the anticipated/estimate reading time per week? I am willing to put hours every day to read these classics, but I work full time and am limited with the hours per day, so want to know whether it would be practically possible for me to read the content. Please share your feedback.

    ReplyDelete
    Replies
    1. Please check out the course web site and email me. We'll keep the time requirements limited -- for E-191 we will be reading a subset of the papers in the list.

      Delete
    2. Thanks professor. Will email you.

      Delete