MIME-Version: 1.0
Server: CERN/3.0
Date: Sunday, 24-Nov-96 22:44:33 GMT
Content-Type: text/html
Content-Length: 18992
Last-Modified: Sunday, 24-Nov-96 20:23:50 GMT
CS472 Fall 96 Course Materials
CS472 Fall 1996
Foundations of Artificial Intelligence
Course Materials
Note: Many of these files are Postscript files (their names
end in ".ps"). No browser we know of can display them directly, so you
either a) have to specify a helper application (like ghostview) to
display them for you, or b) you can download the file and do something
with it locally (for example, in unix you could "lpr" it to a
laser-printer which understands Postscript).
Netscape Navigator in the PC lab, at least on some machines, is
already configured to use ghostview. If you try it, and it doesn't
work, try this.
Tentative Course Syllabus (last modified 11/4)
General Course Information (last modified 9/6)
[html]
Introduction to AI
- (Aug 30) Defining Artificial Intelligence
[ postscript;
postscript, 2 per page;
html ]
- (Sep 02) Uninformed Search
[ postscript;
postscript, 2 per page;
html ]
- (Sep 04) Heuristic Search
[ postscript;
postscript, 2 per page;
html ]
- (Sep 06) Optimal Search
[ postscript;
postscript, 2 per page;
html ]
- (Sep 09) Admissible Heuristics, Adversarial Search
[ postscript;
postscript, 2 per page;
html ]
- (Sep 11) Minimax, Motivation for Alph-beta Pruning
[ postscript;
postscript, 2 per page;
html ]
- (Sep 13) Alph-beta Pruning, State-of-the-Art in Game Playing
[ postscript;
postscript, 2 per page;
html ]
- (Sep 16) Introduction to Machine Learning, K-nn
[ postscript;
postscript, 2 per page;
html ]
- (Sep 18) Decision Tree Learning
[ postscript;
postscript, 2 per page;
html ]
- (Sep 20) Issues in Decision Tree Learning
[ postscript;
postscript, 2 per page;
html ]
- (Sep 23) Learning as Search
[ postscript;
postscript, 2 per page;
html ]
- (Sep 25) The Version Space Algorithm
[ postscript;
postscript, 2 per page;
html ]
- (Sep 27) Genetic Algorithms
[ postscript;
postscript, 2 per page;
html ]
- (Sep 30) Neural Networks: Feedforward Networks
[ postscript;
postscript, 2 per page;
html ]
- (Oct 2) Neural Networks: Backpropagation
[ postscript;
postscript, 2 per page;
html ]
- (Oct 4) ML Applications
[ postscript;
postscript, 2 per page;
html ]
- (Oct 7) History of AI; Rule-Based Systems
[ postscript;
postscript, 2 per page;
html ]
- (Oct 9) Forward Chaining Rule-Based Systems
[ postscript;
postscript, 2 per page;
html ]
- (Oct 16) Backward Chaining Rule-Based Systems
[ postscript;
postscript, 2 per page;
html ]
- (Oct 23) Knowledge Representation: Semantic Nets
[ postscript;
postscript, 2 per page;
html ]
- (Oct 25) Representing Facts in First-Order Logic
[ postscript;
postscript, 2 per page;
html ]
- (Oct 28) Resolution Theorem Proving; Conversion to Clause Form
[ postscript;
postscript, 2 per page;
html ]
- (Oct 30) Unification; Selection of Clauses
[ postscript;
postscript, 2 per page;
html ]
- (Nov 1) Intro to Planning; The Frame Problem
[ postscript;
postscript, 2 per page;
html ]
- (Nov 4) Partial Order Planning (I)
[ postscript;
postscript, 2 per page;
html ]
- (Nov 6) Partial Order Planning (II)
[ postscript;
postscript, 2 per page;
html ]
- (Nov 11) Hierarchical Planning, Reasoning Under
Uncertainty (intro)
[ postscript;
postscript, 2 per page;
html ]
- (Nov 13) Probabilistic Reasoning, Bayesian Inference
[ postscript;
postscript, 2 per page;
html ]
- (Nov 15) Belief Networks
[ postscript;
postscript, 2 per page;
html ]
- (Nov 18) Natural Language Processing (intro)
[ postscript;
postscript, 2 per page;
html ]
- (Nov 20) Syntactic Analysis: top-down parsing
[ postscript;
postscript, 2 per page;
html ]
- (Nov 22) Sentence Analysis: bottom-up chart parsing
[ postscript;
postscript, 2 per page;
html ]
- (Nov 25) Conceptual Sentence Analysis: the CIRCUS parser;
The Problem of Inference
[ postscript;
postscript, 2 per page;
html ]
- (Nov 27) Machine Learning of Natural Language (no on-line notes)
Homework 1 (due Monday, 9/16)[html]
Homework 1 Solutions [html]
Homework 2 (due Monday, 9/30)[html]
Homework 2 Solutions [html]
Lisp code for counting tic-tac-toe games (Homework 2)
Homework 3 (due Wednesday, 10/16)
Homework 3 Solutions
Midterm/Prelim from Fall 1995 (We covered all of the material on that midterm.)[html]
Solution to 1995 Midterm [html]
Solution to 1996 Midterm [html]
Homework 4 ***Note that a clarification for problem 4 was added at 5:30p.m. on
11/6. Here is the clarification: Unless otherwise specified, you can assume that either
(1) the system adds the fact that
JB is a 1973 Dodge Van to the KB at query time, or (2) the fact that JB is a 1973 Dodge
Van already exists in the KB. The postscript document has been modified only to include
this clarification. *** (due Monday, 11/11)
Homework 4 Solutions
Note that program information is also available in the CS472 folder on the j drive
of the PCs.
Program 1 (due Monday, 9/23)[html]
-
rubix.lisp
-
rubix-search.lisp
Program 1 Solution [html]
-
rubix-solution.lisp
Program 2 (due Wednesday, 10/23)[html]
-
general-game.lisp
-
othello.lisp
-
Program 2 Solution [html]
-
minimax-solution.lisp
Program 3 (due Friday, 11/22 *****New due date: Monday 11/25 at
the beginning of class*****)[html]
-
planner.lisp
-
rubix-planner.lisp
Course Syllabus and Project Information (last modified 9/22)
Project Ideas
Format for project proposal (due at class time on Tues 10/1, PC lab)
postscript ,
html
CS473 Due Dates
Format for status reports
postscript ,
html
Here are some examples of code with good procedural and data abstraction as well
as good, consistent indentation.
Courtesy of Ed Wayt and Oumi Mehrotra.
Generic Plan for Finishing the Project On Time: It will be
easier if you write your code in stages. The code reviews provide
intermediate feedback on your progress. Here is how I'd suggest
working on the code. (If, for some reason, you think that your
particular project doesn't fit well into the structure below, let me
know and I can help you create a schedule that does...)
- First, think about the major ``modules'' that your project requires and the
knowledge structures (e.g., rules, state descriptions, board representations) that you'll
need (including any related constructor functions and accessor functions --- as described by
Winston in our main text). Implement the modules as ``stubs,'' i.e., lisp functions that
have no substantive code, but that specify all of the necessary parameters and that make calls
to the appropriate module stubs. Write the code to implement your (generic) knowledge
structures.
(completed for code review 1, 29 Oct)
- Get the system running from beginning to end as soon as possible --- just on a
simple example. This will invariably require making many simplifying
assumptions. Design the inference engine or control strategies needed for your
system. E.g., specific search strategy, rule interpreter, move generator,
learning algorithm.
(completed for code review 2, 18 Nov)
- Finish the implementation of the AI part (inference engine,
control strategies, learning algorithm) of your system. Incrementally
remove the simplifying assumptions by adding the necessary
code. Evaluate the system appropriately. Be sure to leave enough time
for the evaluation --- it is an IMPORTANT component of the final
grade.
(by project end)
Mini-tutorial 1 (introduction to lisp)
Mini-tutorial 2 (list primitives, defining functions)
Mini-tutorial 3 (conditionals, recursion)
Mini-tutorial 4 (data abstraction, mapping, iteration)
Mini-tutorial 5 (debugging, structures, objects)
The Allegro Lisp Editor (the lisp for the PC lab)
Using Lucid Lisp with Emacs (only useful if you have an account on
the CS machines and want to use Common Lisp on those machines rather than the
PC lab)
Common Lisp The Language, Guy Steele
Tulane Common Lisp Tutorial
Johns Hopkins Common Lisp Tutorial
Common Lisp Resouces from CMU AI Repository (including the Lisp FAQ)
Free Common Lisp implementations (from the CMU-AI Lisp FAQ)
Machine Learning Databases at UC Irvine (It's probably best to first
check the end of the page for the README file associated with the data bases.)
Return
to CS472 home page