
Detailed Course Schedule
NOT READY YET
Week 1
Tuesday, Aug 25

Administrivia
Introduction

 Syllabus,
Administrative Note,
Guidelines for reports
 Constraint
Processing 101




Friday, Aug 28 
Topic: Introduction to CSPs
Required reading:
Dechter: Section 1.1, 1.3.3, 1.3.4, 2.1 and 2.2.
Constraint Programming: in Pursuit of the Holy Grail (PS,PDF). Bartak
Recommended reading:
Bartak's online guide: Introduction to CSPs
Constraint Satisfaction (PDF) Rina Dechter. MIT
Encyclopedia of the Cognitive Sciences
Algorithms for Constraint Satisfaction Problems: A
Survey (PDF) by
Vipin Kumar. AI Magazine Spring 1992.
Constraint Satisfaction Problems, An Overview (PDF), Pedro Meseguer
  Constraint
Processing 101
 Homework 1 assigned
 Glossary 1 assigned

Week 2
Tuesday, Sep 2 
Same as above 




Friday, Sep 5 
Same as above 
 Homework 1 due

Week 3
Week 4
Tue Sep 15 
No Class 
Instructor out of town
Glossary 2 due: please give to Shant (GTA).




Friday, Sep 18 
Same as above 

Week 5
Week 6
Week 7
Week 8
Week 9
Tuesday, Oct 20 
No Class 
Fall Break 



Friday, Oct 23 
Topic: Basic Consistency Methods (PPT)
Required reading: The complexity of some polynomial network
consistency algorithms for constraint satisfaction
problemsMackworth/Freuder
Sections 3.1, 3.2, 3.3 of Dechter's book.
Recommended reading:
Sections 3.43.10 of Dechter's book.
Networks of Constraints: Fundamental Properties and
Application to Picture ProcessingMontanari, Information
Sciences, 1974. (Retrieve from instructor.)
Consistency in networks of
relationsMackworth
Constraint propagation with interval
labels, E. Davis
Path Consistency on Triangulated Constraint
Graphs, Bliek, SamHaroud, IJCAI 99

Glossary 6 assigned
Quiz 4

Week 10
Tuesday, Oct 27 
Same as above

Deadline: Progress reports of projects
are due. (Use handin.)
Homework 5 due
Glossary 6 due




Friday, Oct 30 
Same as above 
Same as above 
Week 11
Tuesday, Nov 3 
Same as above 
Glossary 7 assigned




Friday, Nov 6 
Same as above 

Week 12
Glossary 8 assigned
Week 13
Tuesday, Nov 17 
Topic: Advanced Consistency Methods
Required reading: Dechter: Sections 3.1, 3.2, 3.3, 3.4, 3.5.1, 3.5.3, 8.1.
Recommended reading:
Neighborhood Inverse Consistency Preprocessing, Freuder and Elfe
AAAI 96
Optimal
and Suboptimal Singleton Arc Consistency Algorithms, Bessière,
Debruyne, IJCAI 2005
Domain Filtering Consistencies for NonBinary Constraints,
Bessière, Stergiou, and Walsh, AIJ 2008.
Synthesizing constraint expressions, Freuder JACM 1978

Glossary 8 due




Friday, Nov 20 
Same as above 
Deadlines: First deadline for
extracredit work. At most 1 paper presentation, 2
summaries, 1 chapter writeup after this date. 
Week 14
Tuesday, Nov 24 





Friday, Nov 27 
No Class  Thanksgiving Break 

Week 15
Tuesday, Dec 1 
Residues discussion

Maintaining Arc
Consistency with Multiple Residues, Christophe Lecoutre et al.,
Constraint Programming Letters, 2008.
A Study of Residual Supports in Arc Consistency,
Christophe Lecoutre and Fred Hemery. Christophe Lecoutre and Fred Hemery, IJCAI 2007.
Arc Consistency during Search,
Likitvivatanavong et al., IJCAI 2007.
An Optimal CoarseGrained
Arc Consistency Algorithm, Christian BessiÃ¨re et a,
Artif. Intell. 165(2): 165185 (2005).




Friday, Dec 4 
Consistency in nonbinary CSPs 
Deadlines:
Final glossary due, in print and using handin.
Project reports are due in print and using handin.
Second deadline for extracredit work: No paper
presentation, summaries, writeups, on or after this date.

Week 16  Dead Week
Tuesday, Dec 8 





Friday, Dec 11 

Deadline: Project code and slides due, submit using handin.

Week 17  Finals Week
Day/Date: 
To Be Determined

Project Presentations

Last modified: Sun Dec 6 11:01:04 CST 2009
