EngrI/CS 172 : Computation, Information, and Intelligence, Fall 2002

An introduction to computer science using techniques and examples from the field of artificial intelligence. Topics include compute-intensive methods, search techniques, game playing, natural language processing, data mining, the World Wide Web, information retrieval, machine learning, machine translation, the Turing test. This is not a programming course; coursework involves challenging pencil-and-paper problem solving assignments. Some knowledge of calculus will be assumed. Currently, enrollment is not permitted for those who have taken CS100 or have equivalent experience; please contact the instructor if you have questions.

Course Staff and Office Hours (last update 12/6)

Important Course Information (Syllabus | | Enrollment | | Course Materials | Homework and Exams | Academic Integrity)

Another useful site is Cornell's Learning Strategies Center's collection of Study Skills Resources.

Related Sites

Handouts

Some of these links may have access restricted to within Cornell.

Lecture index: Intro to CS: Aug 30 Intro to AI: Sep 2 Problems: Sep 4 Paths: Sep 6 Search: Sep 9 Minimax: Sep 11 Pruning: Sep 13 Problems/learning: Sep 16 ML; perceptrons Sep 18 Perceptrons (cont) Sep 20 Perceptrons (cont) Sep 23 Perceptrons (cont) Sep 25 Nearest neighbors Sep 27 TMs Sep 30 TMs Oct 2 TMs Oct 4 IR Oct 7 B-trees Oct 9 VSM Oct 11 VSM (cont) Oct 16 midterm Oct 18 WWW Oct 21 links Oct 23 hubs/auths Oct 25 in-degrees Oct 28 NLP Oct 30 CFGs Nov 1 CFGs Nov 4 PDAs Nov 6 Discourse Nov 8 Discourse (cont) Nov 11 Zipf's law Nov 13 Federalist papers Nov 15 segmentation Nov 18 MT Nov 20 MT (cont) Nov 22 Stat learning Nov 25 Turing test Dec 2 Turing test (cont) Dec 4 Turing test (cont) Dec 6

8/30: An introduction to computer science (CS) Course information sheet Lecture handout Information about the Newell and Simon reading assignments Allen Newell and Herbert A. Simon. Computer science as empirical inquiry: symbols and search. Communications of the ACM 19(3), March 1976. 9/2: Computer "science"; introduction to artificial intelligence (AI) Further course information Computing experience survey (see me if you haven't filled this out) 9/4: Problem solving and problem spaces Lecture handout 9/6: Problem spaces and problem solving (search) Lecture handout 9/9: Depth-first and breadth-first search 9/11: Game playing: minimax Lecture handout 9/13: Pruning game trees; non-zero-sum games Lecture handout Homework One Office hours 9/16: Conclusion of problem-solving; introduction to machine learning Lecture handout 9/18: Machine learning frameworks; introduction to perceptrons Lecture handout 9/20: The perceptron learning setting, and the necessity of restricting the oracle Lecture handout 9/23: The perceptron learning algorithm Lecture handout 9/25: The perceptron convergence theorem Homework Two 9/27: Nearest-neighbor learning; learning wrap-up Lecture handout 9/30: Introduction to Turing machines Information about the Kleinberg and Papadimitriou reading assignment Jon Kleinberg and Christos Papadimitriou. Computability and Complexity. September 2002 draft of an essay for the National Academies' Study on the Fundamentals of Computer Science. Homework One solutions Lecture handout 10/2: Universality of TMs; the halting function Homework Three 10/4: The incomputability of the halting function Lecture handout 10/7: introduction to information retrieval; Boolean keyword retrieval Lecture handout 10/9: B-trees Lecture handout Solutions to Homework Two Midterm Information handout 10/11: Conclusion of B-trees; introduction to the vector-space model Lecture handout Solutions to Homework Three Part C 10/16: Term-weighting methods Solutions to Homework Three Parts A and B 10/18: Midterm Excerpts from Broder et al., Graph structure in the Web, Proceedings of the Ninth International World Wide Web Conference 33(1-6): 309-320 (2000). Information about the Broder et al. reading Complete Broder et al. paper 10/21: Corpus structure Chakrabarti et al., Hypersearching the Web, Scientific American pp. 54--60 (June 1999). Information on the Chakrabarti et al. reading Midterm solutions and assorted statistics 10/23: Corpus structure (cont); using links to improve IR Homework Four 10/25: Hubs and authorities Lecture handout 10/28: Local Web structure: uniform and preferential attachment Lecture handout 10/30: Introduction to natural language processing Lillian Lee, "I'm sorry Dave, I'm afraid I can't do that": Linguistics, statistics, and natural language processing circa 2001. To appear in the National Academies' Study on the Fundamentals of Computer Science. Information on the NLP reading 11/1: Context-free grammars Homework Five Lecture handout 11/4: Context-free grammars (cont) Lecture handout 11/6: Push-down automata Homework Four solutions Lecture handout 11/8: PDA examples; discourse phenomena Lecture handout 11/11: Grosz and Sidner discourse theory Lecture handout 11/13: Zipf's law Lecture handout 11/15: Statistical authorship identification: The Federalist Papers Lecture handout Alan Turing. Computing Machinery and Intelligence. Mind, New Series, 59(236), October 1950, pp. 433--460. Information about the Turing reading 11/18: Learning to segment Japanese Rie Kubota Ando and Lillian Lee. Mostly-unsupervised statistical segmentation of Japanese: Applications to Kanji. Proceedings of the NAACL, 2000. 11/20: Introduction to machine translation Lecture handout John R. Searle, Minds, Brains, and Programs. The Behavioral and Brain Sciences 3 (3), 1980. (We are reading a "penultimate draft"). Information about the Searle reading 11/22: Statistical machine translation: the Candide algorithm Lecture handout Homework Five solutions Homework Six Exam conflict and office-hour scheduling worksheet 11/25: Statistical learning in humans Jenny R. Saffran, Richard Aslin, Elissa L. Newport, Statistical learning by 8-month-old infants. Science 274(5294), pp. 1926--1928, 1996. 12/2: Introduction to the Turing test paper 12/4: The Turing test and the Chinese Room Stuart M. Shieber, Lessons from a Restricted Turing Test. Communications of the ACM 37(6), pp. 70--78, 1994. 12/6: The restricted Turing test Homework Six Solutions Final Exam Information