Foundations of Artificial Intelligence

CS4700  - Fall 2011 - Hod Lipson
Cornell University

This course uses an i-clicker. If you do not already have one, please get one and register it.

This course uses CMS. If you are registered for the course but do not have an account, please contact the head TA to be added.

Time and Place

Monday, Wednesday, Friday, 11:15am - 12:05pm. Location: HLS B14

First lecture: Wednesday, August 24, 2011
Last lecture: Friday, December 2, 2011

Midterm (in-class): Friday, October 7, 2011. Open books and notes. Non-programmable calculators are allowed, but no phones, laptops, or any other electronic devices. Topics: Informed and uninformed search, local and adversarial search, CSP, Markov models, Reinforcement learning.
Final Exam: Fri, 9 Dec 2011 2:00 PM - 4:30 PM, location TBD. Open books and notes. Non-programmable calculators are admitted, but no phones, laptops, or any other electronic devices. If you are unable to make it please notify the instructor well in advance with justification (email with subject line: "CS4700: Request for final exam makeup")

This is a course parallel to CS 4701 - AI Practicum (register separately, not required)

Course Staff and office hours

Instructor: Hod Lipson
Head TA: Jason Yosniski (contact: cs4700ta-l "at"

Name email Office hours & location
Hod Lipson*  Tuesday + Thursday, 1-4pm, Upson 242
Jason Yosinski*  Thursday 8 - 10, Upson 328
Nikos Karampatziakis*  Thursday 6 - 8, Upson 328
Yue Gao*  Wednesday 3 - 5, Upson 328

Mailing List

* For questions email cs4700ta-l "at" (Note: Remove the extra spaces).  The list is set to mail all the TA's and Prof. Lipson -- you will get the best response time by using this facility, and all the TA's will know the question you asked and the answers you receive. Anything you mail here will only go to the instructors and the TAs, not the entire class.

You can also join the Google group to receive and post announcements relating to this class. Anything you post here will go to the entire class.

Reference Material

The main textbook for the class is: Artificial Intelligence: A Modern Approach, Russell and Norvig, Prentice-Hall, Inc., third edition.  I’ll refer to the book as “R&N”.

Lab accounts

Accounts at the Computer Science Undergraduate Lab (CSUG) should already be set up for all pre-enrolled students over the summer, and for newly registered students by the end of the add-drop period. If you do not have an account but need one sooner, please submit a request. You must authenticate your account before you can start using it. This will also grant you card access to the lab and to the MSDNAA software library for downloading software.

Accounts on CMS should also be set up for all pre-enrolled students. If you do not have an account, please contact the head TA and ask to be added.


This course has no prerequisites other than familiarity with basic data structures and programming (e.g., CS2110) and the basic mathematical skills obtained in CS2800. An understanding of inference in prepositional logic and basic blind search techniques (i.e., breadth-first and depth-first search) is also assumed, but background readings in these topics can be provided for those with a deficiency in this area.

If you have not taken prerequisites but want to take this course anyway, please be aware that there is a significant programming component. Get a copy of Introduction to Algorithms (Cormen et al.) and read and understand the chapters on Elementary Data Structures, Hash tables, Binary Search trees, and Elementary Graph algorithms. Do a few of the exercises to test your knowledge You must be comfortable programming in some high level language.


This course introduces the theoretical and computational techniques that serve as a foundation for the study of artificial intelligence (AI). Topics to be covered include the following:

Note: some of the topics listed above may be covered only briefly, depending on time. Detailed reading information will be provided in the lectures notes and homework assignments.

Grading This is a 3-credit course. Grades will be determined based on a midterm, a final exam, homework assignments, and class participation.

The midterm is an in-class examination (Friday, Oct 7).

The final will be given on the day and time slot scheduled by the university. Please check before you schedule your trip back home for winter break.

Homework assignments are or will be available below and on CMS. Assignments are due in hardcopy in class as well as on CMS. Graded homework assignments and the midterm can be picked-up in Upson 360.

Cooperation on homework assignments. Each student must solve problems and write their own code independently. While students are encouraged to discuss approaches, student must not compare or copy code or jointly write code, or copy it from another source. Students aware of a circulating or posted solution to a homework question must immediately report it to the instructor.

Late submissions. All assignments are due at the beginning of class on the due date. Assignments turned in late will drop 10% for each period of 24 hours for which the assignment is late (including weekends). If you turn in your assignment late, please bring a hardcopy to the head TA. No assignments will be accepted after grading is completed and the grades have been posted on CMS. To accommodate unforeseen situations, use slack days: Each student is allowed to submit an assignment a day late three times (or three days late, once, etc.) without any explanation, for any reason (e.g. sickness, religious, or any personal reason). Please use slack days judicially. Mark the number of remaining slack days at the top of your submission.

Re-grading: Although you are encouraged to talk with any TA about the questions, only the head TAs may award back points (or detract points if they find new things wrong) if you want a re-grade.

Participation: Participation in this course is not mandatory but encouraged. Students that actively participate (by using the clicker) can optionally substitute some of their final exam grade with their participation grade (this will be done automatically to maximize the grade). Participation grade is based on the proportion of class questions you responded to with your clicker. It does not matter if you answered correctly or incorrectly.

Tentative Schedule (dates tend to shift during the semester)

Date Topic Reading (R&N 3rd Edition) Reading (R&N 2nd Edition)
Wed 8/24 About the course    
Fri 8/26 Introduction R&N Ch. 1, 2 R&N Ch. 1, 2
Mon 8/29 Agents and Problem-Solving as Search R&N 3.1-3.4, 11.3 R&N Ch. 3
Wed 9/1      
Fri 8/31
Mon 9/5 Labor day break    
Wed 9/7 Informed Search R&N 3.5-3.6 R&N 4.1-4.2
Fri 9/9
Mon 9/12 Local Search R&N 4.1 R&N 4.3. and p. 120
Wed 9/14      
Fri 9/16 Constraint Satisfaction R&N Ch. 6 R&N Ch. 5
Mon 9/19      
Wed 9/21      
Fri 9/23 Adversarial Search and Games R&N Ch. 5 R&N Ch. 6
Mon 9/26      
Wed 9/28 Markov Decision Processes and policy search R&N 17.1-17.3 R&N 17.1-17.3
Fri 9/30      
Mon 10/3 Reinforcement Learning R&N 21.1-21.4 R&N 21.1-21.4
Wed 10/5      
Fri 10/7 Midterm  
Mon 10/10 Fall break    
Wed 10/12 Instance Based Learning R&N 18.1-18.2, 18.8.1 R&N 18.1-18.2, 20.4
Fri 10/14      
Mon 10/17 Decision Trees R&N 18.3 R&N 18.3
Wed 10/19  
Fri 10/21 Over-fitting and Cross-Validation
Mon 10/24 Statistical Learning Theory R&N 18.5 R&N 18.5
Wed 10/26 Perceptron and Optimal Hyperplanes R&N 18.7 (single layer and multi layer) R&N 20.5 (single layer and multi layer)
Fri 10/28      
Mon 10/31 Neural Nets R&N 18.7
Wed 11/2  
Fri 11/4 Support Vector Machines and Kernels R&N 18.9  
Mon 11/7    
Wed 11/9 Knowledge-Based Systems R&N 7.1-7.6 R&N 7.1-7.6
Fri 11/11      
Mon 11/14 First-Order Logic and Resolution R&N Ch. 8, R&N 9.1-9.3, 9.5 R&N Ch. 8, R&N 9.1-9.3, 9.5
Wed 11/16      
Fri 11/18 Planning R&N 10.1-10.2, 10.4.2-10.4.4 R&N 10.3 (up to page 334), R&N 11.1-3
Mon 11/21      
Wed 11/23 Unsupervised learning R&N 20.3 R&N 20.3
Fri 11/25 Thanksgiving break    
Mon 11/28 Evolutionary Algorithms    
Wed 11/30      
Fri 12/2 The rest of AI    
Fri, Dec 9 Final exam Fri, Dec 9, 2:00 PM HLSB14: Location TBD  


Homework  (due dates may change)

Homework # 1 (Due Sep 16)

Homework # 2 (Due Oct 3)

Homework # 3 (Due Oct 19)

Homework # 4 (Due Nov 4)    Data

Homework # 5 (Due Nov 21)

Homework # 6 (Due Dec ??)

Review Sessions

Review sessions will be held 7pm-9pm in Phillips 203, on the following dates:


Tue Sep 13 Yue (+ Nikos) ,

Thu Sep 22 Jason,

Wed Oct 05 Yue + Jason,

Thu Oct 27 Yue,

Tue Nov 15 Nikos,

Wed Dec 07 in Jason + Nikos.

Academic Integrity

This course follows the Cornell University Code of Academic Integrity. Each student in this course is expected to abide by the Cornell University Code of Academic Integrity. Any work submitted by a student in this course for academic credit is expected to be the student's own work. Collaboration is allowed as prescribed above, but you cannot copy all or part of another student's homework or program --- regardless of whether that copy is on paper or on-line. Violations of the rules (e.g. cheating, copying, non-approved collaborations) will not be tolerated.

Each student must write their own code independently. While students are encouraged to discuss solution approaches, they must not compare or copy code, jointly write code, or copy code from another source. Students aware of a circulating or posted solution to a homework question must immediately report it to the instructor.