Computational Thinking, Fall 2007
Part 1: Programs
Sep 6
"No fear"
The scheme language. Reference: 
How to Design Programs chapters 1, 2, 3, and 5.
Programming and debugging as hypothesis-testing experiment. Reference: Polya, How to Solve It, Part 1.
Programming practice as a scientific methodology. Reference: Newell, The Knowledge Level.
Programming languages as collaborative tools. Reference: Simon, Models of My Life, Chapters 12 and 13.
Sep 13
"Matching"
Predicates, truth, and falsehood. Reference: How to Design Programs chapter 4.
Lists and recursion. Reference: How to Design Programs chapters 9 and 10.
Programs and semantics. Reference: How to Design Programs chapter 8.
The physical symbol-system hypothesis.
Principal reference: Newell and Simon, Computer Science as empirical inquiry focus on Section I: Symbols
Supplementary references:
Brooks, Elephants Don't Play Chess, Robotics and Autonomous Systems (6), 1990, pp. 3–15.
Agre, excerpts from Computation and Human Experience, 1997.
Nilsson, The physical symbol-system hypothesis: status and prospects.
Sep 20
"Action"
Side effects, states and simulation. Technical reference: Rosen, Discrete Mathematics, especially section 11.3.
Intelligence as a computational problem: generative behavior.
Principal reference: Newell and Simon, Computer Science as empirical inquiry focus on Section II: Search
Supplementary references:
Lashley, The problem of serial order in behavior, In Cerebral Mechanisms of Behavior, 1951, pages 112-136.
Pylyshyn, The relevance of computation, Chapter 3 of Computation and Cognition: Toward a Foundation for Cognitive Science, MIT Press, 1984, pages 49-86.
Kirsh, Today the earwig, tomorrow man?, Artificial Intelligence 47 (1991), pages 161-184.
Sep 27
"Following Rules"
Symbols and memory in the explanation of generative behavior; Turing machines. Technical reference: Rosen, Discrete Mathematics, especially section 11.4.
Explaining intelligent behavior as heuristic problem solving. Choice, improvisation and ecological rationality.
Principal reference: Pylyshyn, The relevance of computation, Chapter 3 of Computation and Cognition: Toward a Foundation for Cognitive Science, MIT Press, 1984, pages 49-86.
Supplementary references:
Todd and Gigerenzer, Environments that make us smart: Ecological rationality, Current Directions in Psychological Science 16:3 (2007), pages 167-171.
Agre, Planning and improvisation and Running arguments, Chapters 8 and 9 of Computation and Human Experience, Cambridge 1997, pages 142-178.
Nov 1
Milestone 1: Programming practice.
Part 2: Collaboration
Oct 4
"Real computers"
Circuits and their physical realization. Technical reference: Hillis, The Pattern on the Stone, Chapters 1 and 2, Basic books 1998, pages vii-38.
Is the brain a computer? Is the universe a computer?
Principal references:
Randy Gallistel, "Learning and Representation", to appear in Learning and memory: A comprehensive reference. R. Menzel (Vol Editor) & J. Byrne (Editor). New York: Elsevier
Daniel Dennett, "An Idea is Born" from Darwin's Dangerous Idea
Supplementary references:
Hinton, Rumelhart and McClelland, Distributed Representations, Chapter 3 of Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Volume 1: Foundations, MIT Press, 1986, pages 77-109.
Rumelhart and McClelland, PDP Models and General Issues in Cognitive Science, Chapter 4 of Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Volume 1: Foundations, MIT Press, 1986, pages 110-146.
Karl Sims evolves virtual creatures
Oct 11
"Modules meets emergence"
Turing machines redux. Universality, computability and self-reference. Useful starting points (in addition to Rosen): Wikipedia on Computability, Turing machines and The Halting Problem.
Modularity, specification and the design of complex programs.
Creativity, consciousness and computation.
Principal Reference: Hofstadter, Strange Loops or Tangled Hierarchies, Chapter 20 of Goedel, Escher, Bach, 1979/1999, pages 684-719.
Oct 18
"Complexity"
Asymptotic complexity, and algorithmic effects. Technical reference: Rosen, Discrete Mathematics, especially section 2.2 and 2.3. Useful starting points in Wikipedia: Computational comleixty, Big O and NP completeness.
Fast-growing functions and expressive power. See Scott Aaronson's nice article.
Problematic communication in interdisciplinary teams.
Principal Reference:
Stone, Patton and Heen (no relations), Sort out the three conversations, Chapter 1 of Difficult Conversations: How to Discuss What Matters Most, Penguin 1999, pages 3-20.
Supplementary References:
Stone, Patton and Heen (no relations), Explore each other's stories, disentangle intent from impact, map the contribution system, Chapters 2-4 of Difficult Conversations: How to Discuss What Matters Most, Penguin 1999, pages 25-82.
Stone, Patton and Heen (no relations), Have your feelings, ask yourself what's at stake, Chapters 25-6 of Difficult Conversations: How to Discuss What Matters Most, Penguin 1999, pages 85-128.
Oct 25
"Structured representations"
HTML and XML.
Structured data, semi-structured data, parse trees.
Problematic communication in interdisciplinary teams.
Principal Reference:
Stone, Patton and Heen (no relations), Creating a learning conversation, Chapters 7-10 of Difficult Conversations: How to Discuss What Matters Most, Penguin 1999, pages 131-216, especially Chapters 8 and 11.
Nov 1
Guest lecture by Ken Shan.
"Servers and state"
Servlet programming.
Continuations.
Rohit Parikh, Language as social software, in J. Floyd and S. Shieh, Future Pasts: The Analytic Tradition in Twentieth Century Philosophy, Oxford, 2001, pages 339-350.
Part 3: Computational Science
Nov 8
"Algorithms and insights"
GCD. Balanced trees.
Data as programs: using and interpreting corpora, examples, and experimental results.
References:
Nov 15
"Empirical algorithms"
Heaps. Compression.
Problems, solutions and approximations.
References:
Mike Fourman's lecture notes on binary heaps
Ian Craw's lecture notes on Huffman coding
{liink: Wikipedia on Huffman coding|http://en.wikipedia.org/wiki/Huffman_coding}
Nov 20
"Cognitive algorithms"
Closest match.
Project presentation one.
References:
Kernighan, Church and Gale, A spelling correction program based on a noisy channel model, ACL 1990
Nov 29
"Perception"
Bayesian inference.
Perception as probabilistic inference.
Supplementary references:
Hermann von Helmholtz, Concerning the perceptions in general, in S. Yantis, Readings in Perception.
Dec 6
"Decision"
Dynamic programming.
Project presentation two.
Supplementary references: