Knowledge without appropriate procedures for its use is [mute], and procedure without suitable knowledge is blind. -- Herbert A. Simon, "Artificial Intelligence Systems that Understand" (1977)
Instructor: Prof. Lillian Lee (see homepage for contact information)
Lecture time and location: MWF 10:10-11:00am, Hollister 110
General course description
Prerequisites and related info: Some knowledge of differentiation required; permission of instructor required (and in the past, generally granted) for students who have completed the equivalent of COM S 100. See the 8/26/05 lecture-aid handout for procedure and the Formal Course Description and Policies for more information.
Administrative information and resources
See the Formal Course Description and Policies section on course materials for web-posting policy and handout accesibility.
Note that the conversion program used to post the handouts to the web causes the web versions to use more space or pages than those handed out in class, but the content should be identical.
| Lecture 1 8/26 |
A breezy intro, touching on blender science, true programmability, and the romance of AI | Handouts: (1) "Introduction to CS and AI " lecture aid, (2) Formal Course Description and Policies, (3) background survey. |
| Lecture 2 8/29 |
Problem solving and problem spaces; specification by explicit enumeration | Handouts: lecture aid |
| Lecture 3 8/30 |
More on specifications; implicit specifications | Handouts: lecture aid |
| Lecture 4 9/2 |
More on implicit specifications | Handouts: (1) lecture aid; (2) tip sheet |
| Lecture 5 9/5 |
Systematic search | Handouts: (1) lecture aid; (2) weekly office-hours schedule |
| Lecture 6 9/7 |
Depth-first and breadth-first search; games | Handouts: (1) lecture aid; (2) Homework One |
| Lecture 7 9/9 |
Games; pruning | Handouts: lecture aid |
| Lecture 8 9/12 |
Pruning; Deep Blue | Handouts: lecture aid |
| Lecture 9 9/14 |
Introduction to learning; perceptrons | Handouts: lecture aid |
| Lecture 10 9/16 |
Perceptrons as linear separators; learning perceptrons in the on-line setting | Handouts: lecture aid |
| Lecture 11 9/19 |
The perceptron convergence theorem | Handouts: (1) lecture aid; (2) Homework Two |
| Lecture 12 9/21 |
Practice with perceptrons; the perceptron convergence theorem, continued | Handouts: (1) lecture aid; (2) Homework One Solutions |
| Lecture 13 9/23 |
The perceptron convergence theorem, concluded; further analysis of the PLA | Handouts: lecture aid |
| Lecture 14 9/26 |
Introduction to information retrieval; B-trees | Handouts: lecture aid |
| Lecture 15 9/28 |
The vector-space model; term-frequency weighting | Handouts: lecture aid |
| Lecture 16 9/30 |
Tf-idf weighting | Handouts: (1) lecture aid (2) Prelim info and temporary changes in office hours (3) Reading: Broder et al, 2000, " Graph Structure in the Web" (we distributed excerpts) |
| Lecture 17 10/3 |
The bowtie structure of the Web | Handouts: (1) Midterm and solutions from 2002 (2) Solutions to Homework Two parts A, B, and D |
| Lecture 18 10/5 |
Models for power-law in-degree distributions on the Web | Handouts: (1)lecture aid (2) Solutions to Homework Two part C (3) Chakrabarti et al., 1999, "Hypersearching the Web" |
| "Lecture" 19 10/7 |
Prelim One | |
| Lecture 20 10/12 |
Finish models of in-degree distribution; using links to enhance IR | Handouts: (1) lecture aid (2) Solutions and statistics for Prelim One (3) Homework Three |
| Lecture 21 10/14 |
PageRank and hubs-and-authorities (HITS) | Handouts: lecture aid |
| Lecture 22 10/17 |
Deeper into PageRank; comparison with hubs-and-authorities | Handouts: (1) lecture aid (2) Reading: Lee, 2004, " 'I'm sorry Dave, I'm afraid I can't do that': Linguistics, statistics, and natural language processing circa 2001" |
| Lecture 23 10/19 |
From IR to NLP | Handouts: (1) lecture aid (2) Homework Four |
| Lecture 24 10/21 |
Language structure | Handouts: lecture aid |
| Lecture 25 10/24 |
Context-free grammars | Handouts: lecture aid |
| Lecture 26 10/26 |
Earley's parsing algorithm | Handouts: (1) lecture aid (2) Homework Three solutions |
| Lecture 27 10/28 |
Learning grammars: the bigram case | Handouts: (1) lecture aid (2) Homework Three solutions |
| Lecture 28 10/31 |
The poverty of the stimulus and the sparse data problem; Jelinek-Mercer smoothing; intro to machine translation | Handouts: (1) lecture aid (2) Homework Four solutions, parts A and C (3) Homework Four solutions, part B |
| Lecture 29 11/2 |
Statistical machine translation | Handouts: lecture aid |
| no "lecture" 11/4 |
Prelim Two | |
| Lecture 30 11/7 |
Statistical machine translation (cont.) | Handouts: (1) lecture aid (2) Homework Five (3) Saffran, Aslin, and Newport (1996): Statistical Learning by 8-Month-Old Infants |
| Lecture 31 11/9 |
Statistical learning in infants | |
| Lecture 32 11/11 |
Statistical segmentation of Japanese | Handouts: (1) announcements and followups (2) lecture slides |
| Lecture 33 11/14 |
Grosz and Sidner discourse theory | Handouts: lecture aid |
| Lecture 34 11/16 |
Grosz and Sidner, continued | Handouts: (1) lecture aid (2) Kleinberg and Papadimitriou (2004), Computability and Complexity |
| Lecture 35 11/18 |
Attentional structure in discourse; begin computability | Handouts: (1) lecture aid (2) Turing (1950), "Computing Machinery and Intelligence " (3) Searle (1980), "Minds, Brains, and Programs" |
| Lecture 36 11/21 |
Turing machines | Handouts: (1) lecture aid (2) Homework Six |
| Lecture 37 11/23 |
The halting function | Handouts: (1) lecture aid (2) Solutions to Homework Five |
| Lecture 38 11/28 |
Review and further directions (I) | |
| Lecture 39 11/30 |
Review and further directions (II) | Handouts: (1) final exam guide (first page) (2) Sample
problems and solutions Link: course evaluation site |
| Lecture 40 12/2 |
Turing tests | Handouts: (1) lecture aid (2) Solutions to Homework Six |