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