Mondays, 5:15 - 7:15 p.m. 

Instructor: 
Professor Harry Lewis, lewis@harvard.edu. Office hours change from week to week -- see here.

Teaching Fellow:

Gal Koplewitz, galkop@gmail.com. Office hours: Thursdays 3-4, Maxwell Dworkin second floor lounge.

This course examines papers every computer scientist should have read, from the 1930s to the present. It is meant to be a synthesizing experience for advanced students 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. The idea is to create a unified view of the field of computer science, for students who already know something about it, by replaying its entire evolution at an accelerated frame rate.

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.

Class Format

The class will be taught using Zoom in the Room technology and can be taken either on campus or remotely. Active participation will be expected and will be the basis for grading.

Grading

Grades will be assigned on the basis of preparation for and participation in class discussions. In particular, regular readings and thoughtful attendance and participation are required. There will also be occasional response papers to readings. Especially important parts of papers will be highlighted in advance, so we can read them more easily and focus on the key parts. In the final course project, students will be asked to provide an in-depth discussion of 1) a paper that we covered in the class but should not have included 2) a paper that we have not covered in the class but that the student believes should have been included. There will be no exams.

Prerequisites

CSCI E-124 plus one other 100-level computer science course.

Readings

Papers that we will read are drawn from this master list. All of the papers are either available through the Harvard Library or are available via the class depository.

Kicking Off Class Discussion

We expect everyone to help kick off class discussion. Please sign up here Links to an external site. for specific papers you would like to lead the discussion on!

Piazza

Please sign up and participate in the Piazza forum for our class.

Course Plan (subject to revision)

Class 1 (Monday, January 22, 2018):

Course overview and participant responsibilities.

Reading:

• Joseph Weizenbaum. “ELIZA—A Computer Program for the Study of Natural Language Communication between Man and Machine.”

Class 2 (Monday, January 29, 2018):

Topic 1: Infrastructure

• Gordon Moore. "Cramming More Components onto Integrated Circuits" (1965)

Topic 2: Origins

• George Boole. "An Investigation of the Laws of Thought" (1853)
• Luigi Menabrea and Ada Lovelace. "A Sketch of the Analytical Engine Invented by Charles Babbage" (1842)
• Alan Turing. "On Computable Numbers, with an Application to the Entscheidungsproblem" (1936)

Additional, Optional Reading:

• Gottfried Wilhelm Leibniz. "Preface to the General Science" (1677)
• David Hilbert. "Mathematical Problems" (1900)

Class 3 (Monday, February 5, 2018)

Topic 1: Architecture

• Arthur Burks, Herman Goldstine, and John von Neumann. "Preliminary Discussion of the Logical Design of an Electronic Computing Instrument" (1946)

Topic 2: Information

• Claude Shannon. "A Symbolic Analysis of Relays and Switching Circuits" (1938)
• Claude Shannon. "A Mathematical Theory of Communication" (1948)
• Richard Hamming. "Error Detecting and Error Correcting Codes" (1950)

Additional, Optional Reading:

• Howard Aiken. "Proposed Automatic Calculating Machine" (1938)
• Maurice Wilkes. "The Best Way to Design an Automatic Calculating Machine" (1951)
• Tom Kilburn, D. B. G. Edwards, M. J. Lanigan, and F. H. Sumner. "One-Level Storage System" (1962)
• "Learning Representations by Back-Propagating Errors" (1986)

Class 4 (Monday, February 12, 2018) 

Topic 1: Computers for people

• Vannevar Bush. "As We May Think" (1945)
• C. R. Licklider. "Man-Computer Symbiosis" (1960)
• Douglas Engelbart. "Fall Joint Computer Conference: The Demo" (1968)
• Alan Kay. "A Personal Computer for Children of All Ages" (1972)

Additional, Optional Reading:

• Douglas Engelbart. "Augmenting Human Intellect: A Conceptual Framework" (1962)
• P. Thacker, E. M. McCreight, B. W. Lampson, R. F. Sproull, and D. R. Boggs. "Alto: A Personal Computer" (1979)
• John McCarthy. "The Home Information Terminal" (1970)

NO CLASS on Monday, February 19, 2018 - Presidents' Day 

Class 5 (Monday, February 26, 2018):

Topic 1: Computers and thinking

• Alan Turing. "Computing Machinery and Intelligence" (1950)

Topic 2: Formal models

• Noam Chomsky. "Three Models for the Description of Language" (1956)
• Michael Rabin and Dana Scott. "Finite Automata and their Decision Problems" (1959)

Additional, Optional Reading:

• Claude Shannon. "Programming a Computer for Playing Chess" (1950)
• Claude Shannon. "Computers and Automata" (1953)
• Stephen Kleene. "Representation of Events in Nerve Nets and Finite Automata" (1951)
• Stuart Shieber. "Evidence Against the Context-Freeness of Natural Language" (1985)
• Donald Knuth. "On the Translation of Languages from Left to Right" (1965)

Class 6 (Monday, March 5, 2018)

Topic 1: Software as engineering           

• Grace Hopper. "The Education of a Computer" (1952)
• Frederick Brooks. The Mythical Man-Month (1975)
• Frederick Brooks. No Silver Bullet. (1986)

Topic 2: Artificial Intelligence (Guest: Amanda Gefter)

• John McCarthy, Marvin Minsky, Nathaniel Rochester, and Claude Shannon. "A Proposal for the Dartmouth Research Project on Artificial Intelligence" (1955)
• Warren McCulloch and Walter Pitts. "A Logical Calculus of the Ideas Immanent in Nervous Activity" (1943) (Just a glance!)
• Amanda Gefter. "The Man Who Tried to Redeem the World with Logic" (2015)

Additional, Optional Reading:

• Nancy Leveson and Clark Turner. "An Investigation of the Therac-25 Accidents" (1993)
• Ned Block. "Psychologism and Behavioralism" (1981)

NO CLASS on Monday, March 12, 2018 - Spring Recess

Class 7 (Monday, March 19, 2018)

Topic 1: Programming languages

• W. Backus, R. J. Beeber, S. Best, R. Goldberg, L. M. Haibt, H. L. Herrick, R. A. Nelson, D. Sayre, P. B. Sheridan, H. Stern, I. Ziller, R. A. Hughes, and R. Nutt. "The FORTRAN Automatic Coding System" (1959)
• Peter Naur. "Report on the Algorithmic Language ALGOL 60" (1963)

Additional, Optional Reading:

• James M. Robinette, Martin Wolfe, John Shore, Warren E. Loper, and David Weiss. "Strawman: The Technical Requirements" (1975)
• Alfred Aho, Brian Kernighan, and Peter Weinberger. "Awk - A Pattern Scanning and Processing Language" (1978)

Class 8 (Monday, March 26, 2018)

Topic 1: Graphics and interaction

• Ivan Sutherland. "Sketchpad: A Man-Machine Graphical Communication System" (1963)
• Ivan Sutherland. "The Ultimate Display" (1965)
• T. H. Myer and Ivan Sutherland. "On the Design of Display Processors" (1968)

Topic 2: System design

• H. Saltzer, D. P. Reed, and D. D. Clark. "End-to-End Arguments in System Design" (1983)

Class 9 (Monday, April 2, 2018)

Topic 1: Algorithms

• David Gale and Lloyd Shapley. "College Admissions and the Stability of Marriage" (1962)
• Jack Edmonds. "Paths, Trees, and Flowers" (1965)

Additional, Optional Reading:

• Fernando Corbato, Marjorie Daggett, and Robert Daley. "An Experimental Time-Sharing System" (1962)
• Edsger Dijkstra. "The Structure of the "THE"-Multiprogramming System" (1967)
• Dennis Ritchie and Ken Thompson. "The UNIX Time-Sharing System" (1974)
• Volker Strassen. "Gaussian Elimination is not Optimal" (1969)
• Manuel Blum, Robert Floyd, Vaughan Pratt, Ronald Rivest, and Robert Tarjan. "Time Bounds for Selection" (1972)
• A. R. Hoare. "Quicksort" (1962)
• Lawrence Carter and Mark Wegman. "Universal Classes of Hash Functions" (1979)

Topic 2: Networks

• David Clark. "The Design Philosophy of the DARPA Internet Protocols" (1988)
• Robert Metcalfe and David Boggs. "Ethernet: Distributed Packet Switching for Local Computer Networks" (1976) 

Additional, Optional Reading:

• H. Myer and Ivan Sutherland. "On the Design of Display Processors" (1968)
• Paul Baran. "On Distributed Communications" (1964)
• Vinton Cerf and Robert Khan. "A Protocol for Packet Network Intercommunication" (1974)

Class 10 (Monday, April 9, 2018)

Topic 1: Control abstractions

• Edsger Dijkstra. "Go To Statement Considered Harmful" (1968)
• Leslie Lamport. "Time, Clocks, and the Ordering of Events in a Distributed System" (1978)
• Gray, Lorie, Putzolu, Traiger, "Granularity of Locks and Degrees of Consistency in a Shared Data Base" (1976)

Topic 2: Programs as formalisms

• Robert Floyd. "Assigning Meaning to Programs" (1967)

Additional, Optional Reading:

• Andrew Birrell. "An Introduction to Programming with Threads" (1989)
• A. R. Hoare. "An Axiomatic Basis for Computer Programming" (1969)
• Dana Scott. "Outline of a Mathematical Theory of Computation" (1970)
• Robin Milner. "A Theory of Type Polymorphism in Programming (1977)
• Barbara Liskov, Alan Snyder, Russell Atkinson, and Craig Schaffert. "Abstraction Mechanisms in CLU" (1977)
• Richard De Millo, Richard Lipton, and Alan Perlis. "Social Processes and Proofs of Theorems and Programs" (1979)
• Peter Naur. "Formalization in Program Development" (1982)

Class 11 (Monday, April 16, 2018)

Topic 1: Complexity

• Kurt Godel. "Letter to John von Neumann" (1956)
• Richard Karp. "Reducibility Among Combinatorial Problems" (1972)
• Leonid Levin. "Universal Search Problems" (1973)
• Shafi Goldwasser, Silvio Micali, and Charles Rackoff. "The Knowledge Complexity of Interactive Proof Systems" (1985)

Topic 2: Data organization and retrieval

• Edgar Codd. "Relational Completeness of Data Base Sublanguages" (1972)

Additional, Optional Reading:

• Stephen Cook. "The Complexity of Theorem-Proving Procedures" (1971)
• Karen Spärck Jones. "A Statistical Interpretation of Term Specificity and Its Application in Retrieval" (1972)
• Rudolf Bayer and Edward McCreight. "Organization and Maintenance of Large Ordered Indexes" (1972)
• Salton, A. Wong, and C. S. Yang. "A Vector Space Model for Automatic Indexing" (1975)

Class 12 (Monday, April 23, 2018)

Topic 1: Security and cryptography

• Whitfield Diffie and Martin Hellman. "New Directions in Cryptography" (1976)
• Ken Thompson. "Reflections on Trusting Trust" (1984)
• Ronald Rivest, Adi Shamir, and Len Adleman. "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" (1978)

Topic 2: The Web

• Tim Berners-Lee. "Information Management: A Proposal" (1989)
• Tim Berners-Lee, Robert Cailliau, Jean-François Groff, and Bernd Pollermann. "World-Wide Web: The Information Universe" (1992)

Additional, Optional Reading:

• Shafi Goldwasser and Silvio Micali. "Probabilistic Encryption" (1984)
• Ross Anderson. "Why Cryptosystems Fail" (1993)
• Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. "The PageRank Citation Ranking: Bringing Order to the Web" (1999)

Additional, Optional Course Readings:

Complexity before NP

• Juris Hartmanis and Richard Stearns. "On the Computational Complexity of Algorithms" (1963)
• Manuel Blum. "A Machine-Independent Theory of the Complexity of Recursive Functions" (1967)

Graphical rendering

• Edwin Catmull. "A Subdivision Algorithm for Computer Display of Curved Surfaces" (1974)
• Martin Newell and James Blinn. "The Progression of Realism in Computer Generated Images" (1979)
• Turner Whitted. "An Improved Illumination Model for Shaded Display" (1980)
• James Kajiya. "The Rendering Equation" (1986)

Learning

• Frank Rosenblatt. "The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain" (1958)
• Leslie Valiant. "A Theory of the Learnable" (1984)

General:

• Ivan Sutherland. "Technology and Courage" (1982)