Home
198:503 Computational Thinking Fall 2011
Info
- Class Meetings: Lecture Mon 5-8 in CBIM 22.
- Recitations (50 minutes):
- One of Mon 4-5 in CBIM, Tues 2-3 in CBIM or Thurs 11-12 in RUCCS. Informal review of programming homework and readings. Beginning Sep 26.
Class Meeting Schedule:
Sep 8. Introduction and overview.
- Python programming:
Think Python Chs 1-4 - Mindful problem solving: Excerpt from Polya's How To Solve It
- Programming languages as collaborative tools. Excerpt from Simon's Models of My Life
- Lecture Notes
- Python 2.7.2 download
- Think Python software support: Swampy.
- Exercise: Consult Think Python Ch 4. Go through the code writing tutorial in the chapter, and do some of the exercises until you get bored or stuck.
Sep 12. Representation
- Python programming: Think Python Chs 5-7 and 10.
- Newell and Simon, Computer Science as Empirical Inquiry (Section on Symbols).
- Gallistel and King, Memory and the Computational Brain, Chapters 4,5 and 6.
- Lecture Notes.
- Exercise: Write a function to add one numeral to another; the numerals are lists of binary digits. Write a function to multiply one numeral by another. In both cases, you want to create a list to store the result of the numerical operation.
- Based on binary.py the example done in class.
Sep 19. Computation and search.
- Python programming: Think Python Ch 11.
- Newell and Simon, Computer Science as Empirical Inquiry (Section on Search).
- Rosen, Discrete Mathematics, Ch 11 (Section 11.3 on Finite State Machines without Output)
- Abelson and Sussman, Structure and Interpretation of Computer Programs (Chapter 4 on evaluation).
- Lecture Notes.
- Exercise: Extend an evaluator to handle boolean logic and conditionals. See details in lecture notes.
- Based on calc.py the example done in class.
- Excercise: Look at the DFAs and NFAs in Rosen, pages 764 and 765. Implement them in Python and explore their behavior.
- Based on dfa.py and nfa.py the examples done in class.
Sep 26. Representations and algorithms for search.
- Python programming: Think Python Ch 12 and 13.
- Newell and Simon, Computer Science as Empirical Inquiry (Section on Search).
- Rosen, Discrete Mathematics, Ch 11 (Section 11.3 on Finite State Machines without Output)
- Technical Reference: Russell and Norvig, Artificial Intelligence: A Modern Approach, Third Edition, Chapter 3 on Search.
- Lecture Notes.
- Exercise: Explore the correspondence between NFAs and DFAs via search.
- Based on language.py a slight variant of the example done in class.
- Write code to find strings where two machines disagree and use the code to test the difference between NFA and DFA for simple examples from Rosen.
Oct 3. Putting it all together.
- Python programming: PLY (Lex and Yacc for Python).
- Lecture Notes.
- Example of unification: unify.py
- Example of syntax specification: ast.py
- Exercise: By Oct 24, to hand in. Flesh out the roadmap in the file kbsk.py to complete an interpreter for a forward-chaining logic programming language (a production rule interpreter). Sample programs: member.txt example worked out in class.
Oct 10. General computation.
- Hillis, The Pattern on the Stone, Chapters 1 and 2 (The physical realization of computers).
- Rosen, Discrete Mathematics, Ch 11 (Section 11.4 on Turing Machines)
- Lecture Notes, including links to videos and demos.
Oct 17. Complexity of computation and algorithm design.
- Rosen, Discrete Mathematics, Chapter 2, the growth of functions and the complexity of algorithms.
- Pylyshyn, Computation and Cognition, Chapter 3, the relevance of computation.
- Lecture Notes.
- Python code for searching and sorting: searchsort.py - try this out and see the difference in complexity for yourself!
- Additional examples for forward-chaining (production rule) inference: grammar1.txt (context free parsing), ccg.txt (categorial grammar parsing), plan1.txt (analyzing situations and suggesting actions).
Oct 24. Languages in practical programming: HTML and SQL.
- Lecture Notes.
- Reference on SQL.
- first.py and last.py - example CGI scripts with forms and database access.
Oct 31. Algorithms and insights; collaboration.
- Difficult Conversations, Introduction.
- Difficult Conversations, The "What Happened?" Conversation.
- gcf.py - sample code with Euclid's algorithm and edit distance
- Lecture Notes
Nov 7. Empirical algorithms; collaboration.
- hc.py - sample code for heaps, encoding and Huffman.
- Lecture Notes.
- Difficult Conversations: The feelings and identity conversations.
- Difficult Conversations: Creating a learning conversation.
Nov 14. Learning algorithms and perception.
- Lecture Notes.
- Russell and Norvig, Artificial Intelligence: A Modern Approach, Chapter 18 (Learning from Examples).