Efficient AI Programming (IAIP), Spring 2007

Lec.	Date	Teacher	Content	Slides	Readings	Exercises
1	29-Jan	RMJ	Complexity Class P and NP 1. Overview of IAIP 2. The class P and NP	slides	RN03 1 G04 1 (sup. CLRS03 34)	None
2	05-Feb	RMJ [TH]	NP-Completeness 1. Polynomial-time reductions 2. NP-Completeness 3. Proving NP-Completeness	slides	G04 2 (skim Domination and Independence proof) (sup. CLRS03 34)	exercises solutions
3	12-Feb	RMJ [TH]	Uninformed Search 1. Breadth-first search 2. Depth-first search 3. Depth limited search 4. Bidirectional search	slides	RN03 3 (except 3.6) RN03 2 (skim)	exercises solutions
4	19-Feb	RMJ [TH,MA]	Informed Search 1. Best-First Search (BFS) 2. Greedy search, A* 3. Heuristic functions 4. Local search 5. Hill climbing, simulated annealing, local beam search, genetic algorithms	slides	RN03 4 (except page 102-104, 4.4, and 4.5)	exercises solutions
5	26-Feb	RMJ [TH,MA]	Game Playing 1. Minimax 2. Alpha-Beta pruning 3. Evaluation functions 4. Expectiminimax	slides	RN03 6	exercises solutions
6	05-Mar	RMJ [TH,MA,SA]	Machine Learning 1. Inductive learning 2. Decision tree learning 3. Q-learning	slides	RN03 18.2, 18.3 TM97 13.1, 13.2, 13.3, 13.4	exercises solutions Game project: Description Interface Java files Groups
7	12-Mar	SS [TH,MA,SA]	Propositional Logic 1. Syntax and semantics 2. Logical equivalence 3. Resolution 4. Normal forms 5. Horn clauses 6. SAT solving	slides	RN03 7 (except 7.7)	exercises solutions
8	19-Mar	RMJ [TH,MA,SA]	Binary Decision Diagrams 1. Classical representations: truth tables, two-level and multi-level representations 2. INF normal form 3. Binary Decision Diagrams (BDDs)	slides	A97 1, 2, 3	exercises solutions DPLL project Description Java files
9	26-Mar	RMJ [TH,MA,SA]	BDD-Based Algorithms 1. Build 2. Apply 3. BDD-based configuration	slides HRA	A97 4.1, 4.2, 4.3, 5, 6, 7 J05 JHRZ06	exercises solutions
	02-Apr		Easter break
	09-Apr		Easter break
10	16-Apr	RMJ [TH,MA,SA]	Constraint Satisfaction 1. CSPs 2. Constraint Graphs 3. Backtracking 4. Backjumping 5. Backmarking	slides BBnotes	B05 p.1-13	exercises solutions BDD project: Description Java files
11	23-Apr	TH [TH,MA,SA]	Consistency Techniques 1. Arc consistency 2. i-consistency 3. Directional consistency	slides	B05 p.14-19	exercises solutions
12	30-Apr	RMJ [TH,MA,SA]	Advanced Constraint Solving 1. Forward Checking 2. Partial and Full Look-Ahead 3. Variable and Value Ordering 4. Cycle-Cut set 5. Branch and Bound	slides	B05 p. 28-42 (except Backtrack-free search p.34-35, and Mace p.36-37)	exercises solutions Forward checking project: Description Java files
13	7-May	RMJ [TH,MA,SA]	Repetition + 1. Quantified Boolean Formulas (QBF) 2. BDD-based search	slides	JHRZ06	exercises solutions trialExam1 trialExam2 IAIPfall05Sol IAIPfall05NoSol

Exercises and Projects

Each recitation session will have a number of exercises for you to work on. We strongly recommend that you solve each exercise to consolidate what you have learned and prepare for the exam. The exercises, however, are not mandatory. The implementation projects on the other hand are mandatory. They must each be passed in order to qualify for taking the exam. Notice that, as usual for the Danish university educational system, your course grade is solely based on your performance at the exam.

Literature

The textbook (RN) is available in the bookstore at ITU. It costs DDK 603,- (with student discount). Links to PDFs of notes are provided when allowed by copy right laws. It will be informed by email how to get copies from M97.

Supplementary Literature

The texts listed below are for students that wish to study a topic in more depth. They are not a part of the course syllabus of IAIP.

31.05.07	Error in curriculum: you should read 18.2 and 18.3 not 18.1 and 18.2
29.05.07	Question session moved to Aud. 3
18.05.07	List of students eligible for exam
08.05.07	Official curriculum of IAIP Spring 2007
07.05.07	Question session on Thursday 31.05.07, 13-15 in Aud. 3
07.05.07	Trial exams now available under week 13
20.04.07	Significant changes to exercises for Monday
13.04.07	Slight change to exercises for Monday
26.03.2007	Remember to fill in the course evaluation
26.03.2007	BDD-Based Search moved to lecture 13
23.03.2007	Corrected errors in week 8 exercises
23.03.2007	It is unavoidable that some of you are unable to hand in your projects timely. Requests for extensions are directed to Rune M. Jensen and will be processed on an individual basis.
03.03.2007	Please notice that there are slight changes in the readings for Monday
02.03.2007	Some changes to the exercises for Monday

Lectures:	Mondays 13-15	3A12
Recitations:	Mondays 15-17	3A14 and computer cluster 3A50 and 3A52
Questions:	Thursday 31.05.07	3A12 13-15.
Exam:	Monday June 4, 9-13	3A12

News

Time and Place

Schedule (subject to change)

Exercises and Projects

Literature

Supplementary Literature

Manning

RN03	Russell, S. and Norvig, P., "Artificial Intelligence. A Modern Approach. Second Edition", Prentice Hall, 2003, ISBN 0-13-080302-2.
G04	Goddard, W., "Introduction to Algorithms - Part 3: P, NP Hard Problems", Lecture note, Clemenson University, 2004
TM97	Mitchell, T.M., "Machine Learning", WCB/McGraw-Hill, ISBN 0-07-042807-7, 1997.
A97	Andersen, H.R., "An Introduction to Binary Decision Diagrams", Lecture note, Technical University of Denmark, 1998.
J05	Jensen, R.M., "Quantified Boolean Formulas", Lecture note, 2005.
JHRZ06	Jensen, R.M, Hansen, E.A., Richards, S., Zhou R., "Memory-Efficient Symbolic Heuristic Search", In Proceedings of ICAPS-06, p. 304-313, 2006.
B05	Barták, R., "Constraint Propagation and Backtracking-Based Search: a brief introduction to mainstream techniques of constraint satisfaction", Lecture note CP Summer School, 2005.