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
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.
ReplyDeleteThanks! 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.
DeleteI 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.)
ReplyDeleteI 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.
ReplyDeleteI 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.
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.
ReplyDeleteWhich 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
Penny,
DeleteThanks 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!
Great list- LONG list! a few comments
ReplyDelete1) 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
Bill,
DeleteA 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.
Our back and fourth raises a different question:
DeleteIf 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.
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..
ReplyDeleteThanks. 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!)
DeleteThis comment has been removed by a blog administrator.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteI 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.
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDeleteHi 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.
ReplyDeletePlease 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.
DeleteThanks professor. Will email you.
DeleteEnthusiastic words written in this blog helped me to enhance my skills as well as helped me to know how I can help myself on my own. I am really glad to come at this platform.
ReplyDeleteเช่า โปรเจคเตอร์
It is really a helpful blog to find some different source to add my knowledge. I came into aware of new professional blog and I am impressed with suggestions of author.
ReplyDeleteเล่น forex ให้ รวย
I welcome all the suggestion mentioned in this blog related to new learning skills. It is definitely going to help me to adopt new exited way of learning. I think, others will also feel helpful this blog for their needs.
ReplyDeleteHPE StoreEasy 1650
This is actually good to read content of this blog. A is very general and huge knowledgeable platform has been known by this blog. I in reality appreciate this blog to have such kind of educational knowledge.
ReplyDeleteged เรียน
I found this blog after a long time which is really helpful to let understand different approaches. I am going to adopt these new point to my career and thankful for this help.
ReplyDeleteDell PowerVault MD1400
Mesmerized article written on this blog with other relevant information. It is straight to the point that how we can improve our skills as well as how we can be represented to a new stream of professionalism.
ReplyDeletecustom made shirts
Share great information about your blog , Blog really helpful for us . We read your blog , share most useful information in blog . Thanks for share your blog here .
ReplyDeleteรักษาโรคไมเกรน
I found this blog after a long time which is really helpful to let understand different approaches. I am going to adopt these new point to my career and thankful for this help.
ReplyDeleteforex ไทย
Story of this blog is well written. The writer kept in consideration the grammar very well. Level of English also very well. Lot many new words has been used while writing content of this blog.
ReplyDeleteExpert Advisor คืออะไร
Your blog is very informative. Eating mindfully has been very hard for people these days. It's all because of their busy schedules, work or lack of focus on themselves. As a student I must admit that I have not been eating mindfully but because of this I will start now. It could help me enjoy my food and time alone. Eating mindfully may help me be aware of healthy food and appreciating food.
ReplyDeleteวิเคราะห์ กราฟ forex
Fantastic post, very informative. I wonder why the other specialists of this sector do not notice this. You must continue your writing. I'm confident, you have a great readers' base already!โปรโมชั่น แอร์ เอเชีย
ReplyDeleteIt is really a helpful blog to find some different source to add my knowledge. I came into aware of new professional blog and I am impressed with suggestions of author.
ReplyDeleteHPE MSA2042 Dual Controller
Your post is providing some really good information. I liked its essence and enjoyed reading it. Keep sharing such important posts about this blog and its much more helpful for us .
ReplyDeleteของ sale
The site is really beneficial for everyone to know about this topic. I think if you read blog than you will get some more information from blog. This is really useful blog.
ReplyDeleteติว a level
This is really nice to read content of this blog. A is very extensive and vast knowledgeable platform has been given by this blog. I really appreciate this blog to has such kind of educational knowledge.
ReplyDeleteAsk Price คือ