CS/ENGRI 172: Computing, Information, and Intelligence

An introduction to computer science using methods and examples from the field of artificial intelligence. Topics include game playing, search techniques, learning theory, compute-intensive methods, data mining, information retrieval, the Web, natural language processing, machine translation, and the Turing test. This is not a programming course; rather, "pencil and paper" problem sets are assigned. Not open to students who have completed the equivalent of COM S 100; contact the instructor if you have questions.

Meeting Information

Summer 2003


Amanda Holland-Minkley
Rhodes 403

Course Information and Syllabus

Course Information Handout (jump to Syllabus; Enrollment Information and Policy; Course Materials; Homework and Exams; Coursework; References; Academic Integrity)


Course handouts are available at all hours in the racks outside Upson 303 starting the same day as the course in which they were distributed. Most, but not all, handouts will also eventually be made available here.

Lecture Schedule

Lecture 1 Introduction to CS/ENGRI 172, Computer Science, and Artificial Intelligence Handouts: Course Information Sheet; Waver Form; Defining Computer Science lecture notes; Newell & Simon's Turing Award Lecture reading [notes and full text]
Lecture 2 Newell & Simon and the PSS; Problem Solving and Problem Spaces Handouts: Problem Solving and Problem Spaces lecture notes; Homework 1 due July 1
Lecture 3 More Problem Solving: Path Trees and Search Handouts: Path Trees and Search lecture notes
Lecture 4 Game Playing and Chess Handouts: Game Playing lecture notes
Lecture 5 Pruning, Game Playing and Computer Chess Wrap-Up Handouts: Pruning and Final Thoughts on Chess lecture notes
Lecture 6 Machine Learning and a Machine Learning Framework Handouts: Vector Notation for Function Input lecture notes; Perceptrons and Perceptron Learning lecture notes
Lecture 7 Perceptron Functions and Perceptron Learning Handouts: Perceptron Learning Algorithm lecture notes; Homework 2 due July 8
Lecture 8 Perceptron Learning Algorithm Convergence Theorem Handouts: Proof of PLA Convergence lecture notes; Homework 1 solutions
Lecture 9 Nearest-Neighbor Learning; Turing Machines Handouts: Nearest-Neighbor Learning lecture notes; Turing Machine lecture notes; Kleinberg and Papadimitriou "Computability and Complexity" reading
Lecture 10 Turing Machines and Computability Handouts: Turing Machine Computability lecture notes
Lecture 11 Undecidability of the Halting Function Handouts: Homework 3 due July 15
Lecture 12 Transition from Computation to Information; Information Retrieval Handouts: Information and Intelligence lecture notes; Homework 2 solutions
Lecture 13 B-Trees Handouts: B-Trees Examples lecture notes
Lecture 14 Vector Space Models for IR Handouts: Vector Space Models lecture notes; Midterm information sheet; Excerpts on the Structure of the Web reading
Lecture 15 More Vector Space Models; Using Corpus Structure for IR Handouts: Hypersearching the Web reading
Lecture 16 Bowtie Structure of the Web; Hubs and Authorities Algorithm Handouts: Hubs and Authorities Algorithm lecture notes; Homework 3 solutions; Homework 4 due July 23rd
Lecture 17 Local Structure of the Web Handouts: Mathematical Models of Link Creation lecture notes; Homework 3 grading notes
Lecture 18 Introduction to NLP Handouts: History of Statistical NLP reading; Midterm solutions
Lecture 19 Parsing: Context Free Grammars Handouts: Context Free Grammars lecture notes
Lecture 20 Parsing: X-Bar Theory and Push-down Automata Handouts: Push-down Automata lecture notes
Lecture 21 More PDAs; Discourse Structure Handouts: Discourse Structure lecture notes; Homework 5 due July 30
Lecture 22 Word Distributions in English and Zipf's Law Handouts: Word Frequency Distribution lecture notes; Homework 4 solutions
Lecture 23 Miller's Monkeys; The Federalist Papers
Lecture 23 Statistical Segmentation of Japanese Handouts: Word Segmentation for Japanese reading
Lecture 24 Introduction to Machine Translation
Lecture 25 Statistical Machine Translation Handouts: Machine Translation lecture notes; Final Exam information sheet
Lecture 26 Human Statistical Learning Handouts: Statistical Learning by 8-Month-Old Infants, Saffran, Aslin and Newport reading
Lecture 27 Computer Intelligence: The Turing Test Handouts: Computing Machinery and Intelligence, Turing and Minds, Brains, and Programs, Searle readings
Lecture 28 Modern Computer Intelligence: Implementing the Turing Test Handouts: Lessons from a Restricted Turing Test, Shieber reading