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.

- Summer 2003
## Meeting Information |
- Amanda Holland-Minkley
hollandm@cs.cornell.edu Rhodes 403 255-8957
## Instructor |

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