CMPS 240 - Spring 2007

CMPS 240 - Artificial Intelligence - Spring 2007

General Class Information

The Turk

Instructor: Professor Robert Levinson, [levinson AT soe.ucsc.edu], x2087
Grader: Foaad Khosmood [foaad AT ucsc.edu]
Lectures: Tuesdays and Thursdays, 2-3:45PM, Crown Classroom 203
Office Hours: Wed. 6-8PM E2-255, or by appointment (Also after class in Crown area)
Newsgroup: ucsc.class.cmp240 [off campus access]
[Syllabus] [Material] [Projects][Wiki]
[Class Calendar] includes reading and assignment due dates.

Class Material

Required Reading

AI: Artificial Intelligence: A Modern Approach, Stuart Russell and Peter Norvig. Prentice Hall, Second Edition. 2003 ISBN 0-13-790395-2, Webpage: http://aima.cs.berkeley.edu/
ET: Jaynes, E.T. and G. Larry Brethorstt Probability Theory: Logic of Science. Cambridge Press 2003
CH: the UCSC Reader by Chris Harrison: Determining Satisfiability Through Subtraction And a Binary Constrained XOR Form (BXCF).

References

Rich, Elaine, Knight, Kevin, Artificial Intelligence., Second Edition. McGraw-Hill Book Co.,New York,1990.
David Stirzaker, Elementary Probability , Cambridge University Press - 1994.
Dana Ballard, An Introduction to Natural Computation, The MIT Press, 1997.

Projects (Checkpoints [1], [2], [3], [4])

See also the class Wiki for project updates.

Project	Resources	Students
1. 8-puzzle build oracle ---> look for a "perfect" heuristic rule that always shows the optimal path without look ahead.		Fernando Cabrales, Casey Marshall
2. higher order 10x10 tile puzzle approach (perhaps using quadrants)	Tile Puzzles: A Pattern-Weight Formulation of Search Knowledge Gil Fuchs and Robert Levinson (to be made available)
3. random numbers: learn to predict the output of random number generators.		John Murphy
4. Satisfibility using Subtraction and other enhancements (as in Harrison book)		Greg Levin
5. Satisfiability Canonical Form including resolution and others.If matrix is UNSAT it collapses to an empty row of *s: N/A	Satisfiability Benchmarks and Solvers
6. Zchaff : explain details/insights to class.		Gillian Smith
7. Polynomial time algorithm for prime numbers: learn and explain and apply.		Ji Wong Choi, Neeraj Kumar
8. Knights and Knaves Translator into Sat Matrices.	Knights and Knaves Logic Puzzles	Elizabeth Cassell
9. Existential Graphs to Propositional and First Order Logic Theorem Prover.	EG Page at Stanford	Ryan Ferran

Calendar

Lecture	Assignments (AI, ET, CH and EC=extra credit)
I. Introduction to Expert Systems 1. Tuesday, April 3	AI Text: Chapters 1-3 are mainly review. 6-7 HW0: handout in class. Due Thursday April 5. HW1: Due Thursday April 12: AI Text Exercises: 6.1, 7.4, 7.5, 7.6, 7.8, 7.9 ET: Read Chapter 10. No exercises. CH: Read Chapter 1-2, write an exercise for each chapter and answer it.
2. Thursday, April 5
II. Knowledge Bases and Inference 3. Tuesday, April 10	HW2: Due Thursday April 26 AI Text: Chapters 8-10: 8.2, 8.6adgjk, 9.3, 9.9, 9.11, 9.18, 9.19 ET: Chapters 1-2: 2.1-2.3 CH: Chapters 3-4 Write an exercise for each chapter and answer it. Project checkpoint1 descriptions. Due April 19
4. Thursday, April 12	Discipline and Future of Machine Learning [Quicktime video], Tom Mitchell at CMU. HW1 is due.
5. Tuesday, April 17
6. Thursday, April 19	Project checkpoint1 is due. Checkpoint2 assigned. Due May 3.
III. Reasoning Under Uncertainty 7. Tuesday, April 24	HW3: Due Thursday May 10 AI Text: 14-16 14.3 16.3, 16.7 (prove the problem statement is wrong!!), 16.11 ET: 3: 3.1-3.5 CH: Chapters 5-6 Write an exercise for each chapter and answer it.
8. Thursday, April 26	HW2 is due
9. Tuesday, May 1
IV. Communication: Pattern Matching, Analogy and Retrieval 10. Thursday, May 3	HW4: Due Thursday May 24 Papers and problems to be handed out in class. AI Text: Read: Chap 22 ET: 4: 4.1-4.4 CH: Chapters 7-8 Write an exercise for each chapter and answer it. Project checkpoint2 is due.
11. Tuesday, May 8
12. Thursday, May 10	HW3 is due.
13. Tuesday, May 15	Paper: The Boxer, the Wre stler, and the Coin Flip: A Paradoxof Robust Bayesian Inference and Belief Functions.
14. Thursday, May 17	Project checkpoint 3 is due.
15. Tuesday, May 22	Paper: Pattern-Weight Formulation of Search Knowledge [PS][PDF]
16. Thursday, May 24	HW4 is due Paper: The CG Mars Lander[PS][PDF]
17. Tuesday, May 29	Paper: Pattern Associativity and the Retrieval of Semantic Networks [PS][PDF]
18. Thursday, May 31	Project checkpoint 4 is due.
19. Tuesday, June 5
20. Thursday, June 7	Projects are Due. Final Exam may be handed out.
21. Thursday June 14	Final Exam 8-11am. The final exam will come from material in the lectures, projects and readings. A cumulative take home exam is likely.