Great Works in Computer Science
Meetings: Tuesdays and Thursdays, 11am-12:30pm in MEC
215 (varying location)
Instructor: David
Evans
Web page: http://www.cs.virginia.edu/evans/greatworks/
Office hours: Mondays, 1-2pm; Thursdays, 12:30-1:30pm (after class); other times by appointment (when my door is open, you are always free to stop by).
Goal
Computer scientists have a tendency to ignore the past, reinventing things that have been previously discovered and repeatedly relearning the same lessons. The goal of this seminar is to deeply understand some of the great works in computer science. What is a great work? A great work could be a written work, but could also be an algorithm, system, architecture, or methodology. To be "great", it must have lasting value and substantial impact. Great works change the course of computing in ways that become so ingrained in our thinking that people assume that they are how things must have always been, rather than something that was invented and developed.Project
Students will be expected to identify one great work in computer science, justify why it is great, and produce some artifact that illuminates this work. The artifact you produce should be something of value to people beyond just those in the seminar such as a web application, video, software simulation, or paper.Evaluation
Students will be evaluated based on their contributions to the class including participating in the discussions, written responses to the readings, and course projects.Readings
The first readings from the class will be Alan Turing's On Computable Numbers, with an Application to the Entscheidungsproblem (1936) and Charles Petzold's The Annotated Turing.
Later readings will be selected from among the great works in computer science based on student interests and projects. Possible topics include:- Boolean logic: Claude Shannon, A Symbolic Analysis of Relay and Switching Circuits (1938)
- Architecture: John von Neumann, First Draft of a Report on the EDVAC (1945); Caches: Maurice Wilkes, Slave Memories and Dynamic Storage Allocation
- Information Theory: Claude Shannon, A Mathematical Theory of Communication (1948)
- Programming Languages: Revised Report on the Algorithmic Language Algol 60 (1958/1963); John Backus, Can Programming Be Liberated from the von Neumann Style? (1978)
- Algorithms: Tony Hoare, Quicksort; Dijkstra's algorithm (shortest path); Jack Edmonds, Paths, Trees, and Flowers (1963).
- Complexity: Stephen Cook, The Complexity of Theorem-Proving Procedures (1971); Richard Karp, Reducibility Among Combinatorial Problems (1972).
- Vision: Vannevar Bush, As We May Think (1945); J.C.R. Licklider and Robert Taylor, The Computer as a Communication Device (1968); Tim Berners-Lee, Information Management: A Proposal (1989/1990)
- Networking: Metcalfe and Boggs, Ethernet: Distributed Packet Switching for Local Computer Networks (1975); TCP/IP - David Clark, The Design Philosophy of the DARPA Internet Protocols (1988)
- Operating Systems: Robert Daley and Jack Dennis, Virtual Memory, Processes, and Sharing in MULTICS (1968); Dennis Ritchie and Ken Thompson, The UNIX Time-Sharing System (1974).
- Artificial Intelligence: Alan Turing, Computing Machinery and Intelligence (1950); Herbert Simon, The Sciences of the Artificial (1969; revised in 1981 and 1996); Arthur Samuel, Some Studies in Machine Learning Using the Game of Checkers (1959 and 1967 follow up)
- Distributed systems: E. W. Dijkstra, Solution of a Problem in Concurrent Programming Control (1965); Tony Hoare, Communicating Sequential Processes (1978; and 1985)
- Software Engineering: Fred Brooks, The Mythical Man-Month (1975); Barbara Liskov, Alan Snyder, Russell Atkinson, Craig Schaffert, Abstraction Mechanisms in CLU (1977)
- Human-Computer Interaction: Ivan Sutherland, Sketchpad: A man-machine graphical communication system (1963); Douglas Engelbart, Augmenting Human Intellect: A Conceptual Framework (1962) [Demo (1968)]
- Cryptography: Whitfield Diffie and Martin Hellman, New Directions in Cryptography (1976); Rivest, Shamir, Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
- Security: Saltzer and Schroeder, The Protection of Information in Computer Systems (1973/1974); Ken Thompson, Reflections on Trusting Trust (1987)
- Quantum Computing: Richard Feynman, Simulating Physics with Computers (1981)
