Monday, October 15, 2012

A computer science reading list

In writing Computing for Ordinary Mortals, I had to think about where to point readers who might want more depth in each of the topics I wrote about. The result (in the Further Reading sections and end notes) is a reading list for someone who would like to come up to speed in computer science. My choices are biased, of course (a systems person would have more to say about architecture, operating systems, and networking), but I think they're plausible overall.


What is computing?

General reading
W. Daniel Hillis, The Pattern on the Stone: The Simple Ideas that Make Computers Work (Basic Books, 1999).
Allen Newell, Alan Perlis, and Herbert Simon, “What is computer science?” Science, 157 (1967), pp. 1373-4.
Ian Horswill, “What is computation?” ACM XRDS 18, 3 (March 2012), pp. 8-14.
Herbert Simon, The Sciences of the Artificial (MIT Press, 3rd edition, 1996).
Textbooks
Brian W. Kernighan, D is for Digital: What a well-informed person should know about computers and communications (CreateSpace, 2012).
Selected further reading
Paul Rosenbloom, On Computing: The Fourth Great Scientific Domain (Cambridge University Press, 2012).
Interim Review Task Force, Association for Computing Machinery, Computing Curricula Computer Science Volume (2008).
Committee on Information Technology Literacy, National Research Council, Being Fluent with Information Technology (National Academies Press, 1999).
Peter Denning, “Great Principles in Computing Curricula,” ACM Technical Symposium on Computer Science Education (2004).
Donald Knuth, “Computer science and its relation to mathematics,” The American Mathematical Monthly, 81, 4 (1974), pp. 323-343.
Jeanette Wing, “Computational thinking,” Communications of the ACM, 49, 3 (2006), pp. 33-35.
Committee for the Workshops on Computational Thinking, National Research Council, Report of a Workshop on The Scope and Nature of Computational Thinking (National Academy of Sciences, 2009).


A partial history of computing

General reading
James Essinger, Jacquard’s Web: How a Hand-Loom Led to the Birth of the Information Age (Oxford University Press, 2003).
Charles Babbage, Passages from the Life of a Philosopher (Longman, Green, Longman, Roberts, and Green, 1864), pp. 116-117.
Ada Augusta and L. F. Menabrea“Sketch of the Analytical Engine invented by Charles Babbage, by L. F. Menabrea, with notes upon the memoir by the translator Ada Augusta, Countess of Lovelace.
Denise Gürer, “Pioneering women in computer science,” Communications of the ACM, 38, 1 (1995), pp. 45-54.
W. Barkley Fritz, “The women of ENIAC,” IEEE Annals of the History of Computing, 18, 3 (1996), pp. 13-28.
Selected further reading
Alan G. Bromley, “Charles Babbage’s analytical engine, 1838,” IEEE Annals of the History of Computing, 20, 4 (1998), pp. 29-45.
John von Neumann, “First Draft of a Report on the EDVAC”, Moore School of Electrical Engineering, University of Pennsylvania (June 30, 1945).


Computer architecture

General reading
Charles Petzold, Code: The Hidden Language of Computer Hardware and Software (Microsoft Press, 2010).
Textbooks
John L. Hennessy and David A. Patterson, Computer Architecture: A Quantitative Approach (Morgan Kaufmann, 4th edition, 2006).
Miles J. Murdocca and Vincent P. Heuring, Computer Architecture and Organization: An Integrated Approach (John Wiley & Sons, 2007).
Selected further reading
Donald Knuth, “An empirical study of FORTRAN programs,” Software—Practice and Experience, 1 (1971), pp. 105-133.
David Patterson, “The Future of Computer Architecture,” Version 3, December, 2008.


Algorithms and structured data

General reading
John MacCormick, Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today’s Computers (Princeton University Press, 2012).
Textbooks
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms (MIT Press, 3rd edition, 2009).
Selected further reading
Donald Knuth, The Art of Computer Programming (Addison-Wesley).
C. A. R. Hoare, “Algorithm 63: Partition” and “Algorithm 64: Quicksort,” Communications of the ACM, 4, 7 (1961), p. 321.


Programming

General reading
George Polya, How to Solve It (Princeton University Press, 2nd edition, 1957).
Alan Kay, “Computer software,” Scientific American, 251, 3 (1984), pp. 41-47.
Paul Graham, Hackers and Painters: Big Ideas from the Computer Age (O’Reilly, 2004).
C. H. Waddington, Tools for Thought: How to Understand and Apply the Latest Scientific Techniques of Problem Solving (Basic Books, 1977).
Textbooks
Mark J. Guzdial and Barbara Ericson, Introduction to Computing and Programming in Python, A Multimedia Approach (Prentice Hall, 2nd edition, 2009).
Harold Abelson and Gerald Jay Sussman with Julie Sussman, Structure and Interpretation of Computer Programs (MIT Press, 2nd edition, 1996).
Selected further reading
Peter Norvig, Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, (Morgan Kaufmann, 1992).
Frederick P. Brooks, Jr., The Mythical Man-Month: Essays on Software Engineering (Addison-Wesley, 20th Anniversary Edition, 1995).
Niklaus Wirth, Algorithms + Data Structures = Programs (Prentice Hall, 1976).
John W. Backus, “Automatic programming: properties and performance of FORTRAN systems I and II,” the Proceedings of the Symposium on the Mechanisation of Thought Processes, The National Physical Laboratory, England, pp. 232-255.
John W. Backus, “The history of FORTRAN I, II and III,” ACM SIGPLAN Notices - Special Issue: History of Programming Languages conference, 13, 8 (1978), pp. 165-180.
Jon Bentley, Programming Pearls (Addison-Wesley, 2nd edition, 1999).
Andy Oram and Greg Wilson, Beautiful Code: Leading Programmers Explain How They Think (O’Reilly, 2007).
Edsgar Dijkstra, “Go-to statement considered harmful,” Communications of the ACM, 11, 3 (1968), pp. 147-148.
Ruven Brooks, “Towards a theory of the comprehension of computer programs,” International Journal of Man-Machine Studies, 18, 6 (1983), pp. 543-554.
David Parnas, “On the criteria to be used in decomposing systems into modules,” Communications of the ACM, 15, 12 (1972), pp. 1053-1058.


Operating systems

Textbooks
Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne, Operating System Concepts (John Wiley & Sons, 8th edition, 2008).
Andrew S. Tanenbaum and Albert S. Woodhull, Operating Systems: Design and Implementation (Prentice Hall, 3rd edition, 2006).
Selected further reading
Jerome H. Saltzer, “Protection and the control of information sharing in Multics,” Communications of the ACM, 17, 7 (July 1974), 388-402.


Networking and related topics

General reading
Vannevar Bush, “As We May Think,” Atlantic Magazine (July, 1945).
Vannevar Bush, Science: The Endless Frontier (U.S. Government Printing Office, 1945).
Ted Nelson, Computer Lib/Dream Machines (1974).
J.C.R. Licklider, “Man-computer symbiosis,” IRE Transactions on Human Factors in Electronics, 1 (1960) pp. 4-11.
J.C.R. Licklider and R.W. Taylor, “The computer as a communication device,” Science and Technology, 76, 2 (1968), pp. 21-31.
Ian H. Witten, Marco Gori, and Teresa Numerico, Web Dragons: Inside the Myths of Search Engine Technology (Morgan Kaufmann, 2006).
Textbooks
James F. Kurose and Keith W. Ross, Computer Networking: A Top-Down Approach (Addison-Wesley, 2010).
Selected further reading
Ted Nelson, “Complex information processing: a file structure for the complex, the changing and the indeterminate,” Proceedings of the 20th ACM National Conference, pp. 84-100.
J.C.R. Licklider, “Memorandum for members and affiliates of the intergalactic computer network” (1963).
Leonard Kleinrock, “An early history of the Internet [History of Communications],” Communications Magazine, IEEE, 48, 8 (2010), pp. 26-36.
Barry M. Leiner, Vinton G. Cerf, David D. Clark, Robert E. Kahn, Leonard Kleinrock, Daniel C. Lynch, Jon Postel, Larry G. Roberts, and Stephen Wolff, “A brief history of the Internet,” ACM SIGCOMM Computer Communication Review, 39, 5 (2009), pp. 22-31.
David D. Clark, “The design philosophy of the DARPA Internet protocols,” SIGCOMM Computer Communication Review, 18, 4 (1988), pp. 106-114.


Theory

General reading
David Evans, Introduction to Computing: Explorations in Language, Logic, and Machines.
David Harel, Computers Ltd.: What They Really Can’t Do (Oxford, 2000).
Joseph Weizenbaum, Computer Power and Human Reason (W.H. Freeman, 1976).
Douglas Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid (Vintage, 1980).
Textbooks
Michael Sipser, Introduction to the Theory of Computation (International Thomson Publishing, 1996).
John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (Prentice Hall, 3rd edition, 2007).
Alan P. Parkes, A Concise Introduction to Languages and Machines (Springer, 2008).
Selected further reading
MIT Technical Translation of Konrad Zuse, “Rechnender Raum,” Schriften zur Datenverarbeitung, 1 (Friedr. Viewag & Sohn, 1969).
Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 2, 42 (1936), pp. 230–265.
Jack Copeland, “The Church-Turing thesis,” The Stanford Encyclopedia of Philosophy, Edward N. Zalta, editor (Fall, 2008).
Torkel Franzén, Gödel’s Theorem: An Incomplete Guide to Its Use and Abuse (A. K. Peters, 2005).
Stephen A. Cook, “The complexity of theorem-proving procedures,” Proceedings of the Third Annual ACM Symposium on the Theory of Computing (1971), pp. 151-158.
Richard M. Karp, “Reducibility among combinatorial problems,” Proceedings of a Symposium on the Complexity of Computer Computations (Plenum Press, 1972), pp. 85-103.


Artificial Intelligence

General reading
Nils J. Nilsson, The Quest for Artificial Intelligence (Cambridge, 2010).
Simon Blackburn, Think (Oxford University Press, 1999).
Pamela McCorduck, Aaron’s Code: Meta-Art, Artificial Intelligence, and the Work of Harold Cohen (W. H. Freeman, 1990).
Textbooks
Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, (Prentice Hall, 3rd edition, 2010).
Thomas Mitchell, Machine Learning (McGraw Hill, 1997).
Selected further reading
Alan Turing, “Computing machinery and intelligence,” Mind, 59, 236 (1950), pp. 433-60.
Paul R. Cohen, “If not Turing’s test, then what?” AI Magazine, 26, 4 (2006), pp. 61-67.
Allen Newell and Herbert A. Simon, “Computer science as empirical inquiry: Symbols and search,” Communications of the ACM, 19, 3 (1976), pp. 113-126.
Nils J. Nilsson, “The physical symbol system hypothesis: Status and prospects,” Max Lungarella, Rolf Pfeifer, Fumiya Iida, and Josh Bongard (editors), 50 Years of Artificial Intelligence, Lecture Notes In Computer Science, 4850 (Springer, 2007), pp. 9-17.
M. Ross Quillian, “Semantic Memory,” Semantic Information Processing, Marvin Minsky, editor (MIT Press, 1968), pp. 227-270.
John Searle, “Minds, Brains and Programs,” Behavioral and Brain Sciences, 3, 3 (1980), pp. 417–457.
Allen Newell, “The knowledge level: Presidential Address,” AI Magazine, 2, 2 (1981), pp. 1-20.
Rodney Brooks, Cambrian Intelligence: The Early History of the New AI (MIT Press, 1999).
J. Alan Robinson, “A machine oriented logic based on the resolution principle,” Journal of the Association for Computing Machinery, 12 (1965), pp. 23-41.
Thomas G. Dietterich, “Machine Learning,” Nature Encyclopedia of Cognitive Science (Macmillan, 2003).
Claude Shannon, “A mathematical theory of communication,” Bell System Technical Journal, 27 (1948), pp. 379-423 and 623-656.
Allen Newell, J. C. Shaw, and Herbert A. Simon, “Elements of a theory of human problem solving,” Psychological Review, 65, 3 (1958), pp. 151-166.


Human-Computer Interaction

General reading
Donald Norman, The Design of Everyday Things (Doubleday, 1990).
Richard Harper, Tom Rodden, Yvonne Rogers, and Abigail Sellen, Being Human: Human-Computer Interaction in the Year 2020 (Microsoft Research, 2008).
Textbooks
Ben Shneiderman and Catherine Plaisant, Designing the User Interface: Strategies for Effective Human-Computer Interaction (Addison-Wesley, 2009).
Frank E. Ritter, Gordon D. Baxter, and Elizabeth Churchill, The ABCs of HCI (lulu.com, 2002).
Harold Thimbleby, Press On: Principles of Interaction Programming (MIT Press, 2007).
Selected further reading
Ivan Sutherland, Sketchpad—A Graphical Man-Machine Interface (MIT Press, 1963).
J. C. Shaw, “JOSS: a designer’s view of an experimental on-line computing system,” Proceedings of the Fall Joint Computer Conference, Part I (ACM Press, 1964).
Jeff Johnson, Teresa L. Roberts, William Verplank, David C. Smith, Charles H. Irby, Marian Beard, and Kevin Mackey, “The Xerox Star: A Retrospective,” IEEE Computer, 22, 9 (1989), pp. 11-26.
Paul Dourish, Where the Action Is: The Foundations of Embodied Interaction (MIT Press, 2001).
Ross Koppel, Joshua P. Metlay, Abigail Cohen, Brian Abaluck, A. Russell Localio, Stephen E. Kimmel, and Brian L. Strom, “Role of computerized physician order entry systems in facilitating medication errors,” Journal of the American Medical Association, 293, 10 (2005), pp. 1197-1203.
John D. Gould and Clayton Lewis, “Designing for usability: Key principles and what designers think,” Communications of the ACM, 28, 3 (1985), pp. 300-311.

1 comment:

  1. Nice post.The importance of a technical translation being accurate and efficient can indeed not be overstated. Especially in the ever faster moving world of globalized business, successful information and technology transfer within multinational businesses can make the difference between win or lose.

    ReplyDelete