Home
### 198:503 Computational Thinking Fall 2011

### Info

### Class Meeting Schedule:

### Sep 8. Introduction and overview.

### Sep 12. Representation

### Sep 19. Computation and search.

### Sep 26. Representations and algorithms for search.

### Oct 3. Putting it all together.

### Oct 10. General computation.

### Oct 17. Complexity of computation and algorithm design.

### Oct 24. Languages in practical programming: HTML and SQL.

### Oct 31. Algorithms and insights; collaboration.

### Nov 7. Empirical algorithms; collaboration.

### Nov 14. Learning algorithms and perception.

### Nov 28. Learning algorithms and action.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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.

- 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).

- Lecture Notes.
- Reference on SQL.
- first.py and last.py - example CGI scripts with forms and database access.

- Difficult Conversations, Introduction.
- Difficult Conversations, The "What Happened?" Conversation.
- gcf.py - sample code with Euclid's algorithm and edit distance
- Lecture Notes

- hc.py - sample code for heaps, encoding and Huffman.
- Lecture Notes.
- Difficult Conversations: The feelings and identity conversations.
- Difficult Conversations: Creating a learning conversation.

- Lecture Notes.
- Russell and Norvig, Artificial Intelligence: A Modern Approach, Chapter 18 (Learning from Examples).