COMS W 4701
Artificial Intelligence
Spring 2013
Tuesday/Thursday 2:403:55PM
Room: 833 MUDD
CVN Course
Office
Hours: 1 hour prior to class
URL
of this page:
http://www.cs.columbia.edu/~sal/AISpring13.htm
Can you guess what this picture means?
Text Book
Artificial
Intelligence, A Modern Approach,
Russell and Norvig, (Prentice Hall), THIRD
EDITION,
ISBN: 0558881173
URL: http://aima.cs.berkeley.edu/

Overview of AI: Strong, Weak, History, Symbolic AI/Cognitive AI
 Introduction
to LISP: Examples (LISP is NOT required for projects)

Assignment #1: TBA

Problem Solving:
*
Problem Formulation as Search, State Spaces, Problem Reduction
*
Basic Weak Search Methods & Algorithms: Breadth, Depth, Bestfirst,
Generate and Test, Hill Climbing, etc.
*
Assignment #2: Implementation of a basic search method for a moderatescale
problem, comparative evaluation of alternative search algorithms.
*
Game Playing: Minimax, AlphaBeta
*Assignment
#3: Game Playing Tournament, TBA

First Order Logic (Deduction)
*
Mechanical Theorem Proving
*
Unification
*
Gödel’s theorems, SAT and relationship to NPCompleteness

Midterm: Closed Book

Knowledge Representation:
*
Structured Representations: Semantic Nets, Frames, Blackboards, Rules
 Uncertainty and Bayesian Inference (Abduction)

Machine Learning and Generalization (Induction)
*
Inductive Inference
* Version Spaces, ID3, CART,
etc.
*
Bayesian Learning
*
Support Vector Machines
* Assignment
#4: Implementation of a machine learning program classifier

Final Exam: Closed Book, Entire Material Presented in Class
There are many code examples
on the AIMA website to guide your work in LISP and Java.
LISP IS NOT REQUIRED
FOR THE PROJECTS EXCEPT THE FIRST ONE.
Python may be the one
for you!
You Must Read: Lisp vrs Python:
http://norvig.com/pythonlisp.html
[For those who are brave
enough:
LISPworks
(http://www.lispworks.com/) is free and
probably the easiest LISP implementation for you to use. The course structure by lecture is specified
in the table below, annotated with required book chapters from Russel & Norvig’s AIMA
text. Useful slides/code/background material are provided in the right most column. Some of
these are likely to change from time to time.]
The
basic required chapters of AIMA are 14, 510, 13, 14 and 18, 19.
We
will follow a general theme throughout the progression of the course describing
alternative styles of logical inference, from Deductive Inference, to Abductive and finally Inductive
Inference in the context of an intelligent agent
architecture. Autoepistemic will have to wait for another course.
Session 
Date 
Topic/chapter 
Free
code/ HW
Project Assigned or Due 
1 
1/22 
Overview
of AI (Chapter 1 and 2) 
IntroSlides and Agents, Symbolic AI/Cognitive AI 
2 
1/24 
CLICK
ON THIS LINK–History
of AI/LISP 
Project#1: Simple Pattern Matcher MUST BE IN LISP Pattern Match Function Code
– A general schema 
3 
1/29 
Intro
to LISP (to
understand code examples) Equality
of symbol structures 
Download
personal edition Lisp from www.lispworks.com See
http://www.cs.berkeley.edu/~russell/code/doc/install.html 
4 
1/31

Intro
Problem Solving Click on the title and watch Lecture 4 (Chp 3) 
LAST
DAY TO DROP. PLEASE DON’T GO. 
5 
2/5 
Weak
search methods&algs 

6 
2/7 
IDDFS,
Complexity measures 
Project
#1 DUE 
7 
2/12 
Uniform
cost, Greedy, 

8 
2/14 
Heuristic
Search A* (Chp 4) 
Project#2: Search programs, 
9 
2/19 
Beyond
Classical Search (Chpt 4) Heuristic
Admissibility/consistency 

10 
2/21 
Problemreduction
problem solving, Constraint satisfaction problems (Chpt
6) 

11 
2/26 
AND/OR 

12 
2/28 
Game
Playing (Chp 5) 

13 
3/5 
Minimax/Alphabeta 
Project
#2 DUE TUESDAY March 5 
14 
3/7 
Hill
Climbing/Simulated Annealing/Genetic Algs 

15 
3/12 
All
material on search, up to the lecture on 3/12 1
hr 15 min. time limit Propositional
logic is NOT covered on the exam. 

16 
3/14 
Intro
to Knowledge Representation 
Go
over the MIDTERM 

3/183/22 
SPRING BREAK 

17 
3/26 
Propositional
Logic Mechanical
Theorem Proving (Chpt 7,8) 

18 
3/28 
Resolution
Thm. Proving (Chp 9) 

19 
4/2 
First
Order Logic, Godel Thms.
(Chp 8) Resolution
Thm Proving in FOL (Chp 9) 

20 
4/4 
More
logic 
Theorem Proving Code & examples Project
#3 DUE TUESDAY
2 April FOR ALL INCLASS AND CVN STUDENTS . If
you love logic, prove 2+2=4 
21 
4/9 
Semantic
nets/Frames Frames,
Rulebased Systems 
TOURNAMENT
PLAYOFFS FRIDAY APR 5 Pictures from the Tournament
Play from 2013 
22 
4/11 
Uncertainty
(Chp 13, 14) 

23 
4/16 
Bayesian
Inference 

24 
4/18 
Intro
to Machine Learning (Chp 18) 

25 
4/23 
Generalization,
Inductive Inference (Chp 19) 

26 
4/25 
Decision
Tree Learning Naive
Bayes Classifier 

27 
4/30 
Unsupervised
Learning 

28 
5/2 
LAST CLASS – INCLASS FINAL EXAM 
Resurgence
of AI – or more of the same? 
5/7 
Project
#4 DUE TUE 7 MAY, 2013 In
case I’m late, this is filler time. 




End
of Spring 2013 TERM. Summer Break begins. Hurray. I will miss you. 
Grading Policy
Project Submission Instructions
AIMA Code base:
Just visit their link http://www.cs.berkeley.edu/~russell/code/doc/install.html
TA Details 
Probable Final Grade Distribution Final
grades are curved. The
distribution is tentatively set at 

Name:
Adrian Tang (Head TA) Email:
atang@cs.columbia.edu Office:
TA Room (Mudd
122a) TA
office hours:
Wed
68pm Name:
John Sizemore Email: jcs2213@columbia.edu Office: TA
Room (Mudd 122a) TA
office hours: Tue
46pm Name:
Tingting Ai Email: ta2355@columbia.edu Office: TA
Room (Mudd 122a) TA
office hours: Thu
10am12pm Name:
Kangkook Jee Email: jikk@cs.columbia.edu Office: CSB
504 TA
office hours: Mon
10am12pm Name:
Qiuzi Shangguan Email: qs2130@columbia.edu Office: TA
Room (Mudd 122a) TA
office hours: Fri
4pm6pm 
