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 on-line 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

Tuesday, Sep 8	Same as above	Glossary 1 due Glossary 2 assigned.
Friday, Sep 11	Topic: Backtrack Search Required reading: Hybrid algorithms for the constraint satisfaction problem (PDF)--Prosser Recommended reading: Chapters 5 and 6, Dechter Chapter 5, Tsang Lecture notes of Fahiem Bacchus: Chapter 2, Section 2.4 (available upon demand)	Quiz 1 Homework 2 assigned

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

Tuesday, Sep 22	Topics: Same as above Lookahead Schemas (PPT) Required reading: Same as above. Dechter Sections 5.3.1 and 5.3.2/li> Recommended reading: Same as above	Glossary 3 assigned Homework 2 due delayed until Sep 24 Homework 3 assigned
Friday, Sep 25	Topics: Lookahead Schemas (PPT) Continuation of CSP 101: Overview: advanced solving techniques and research directions Required reading: Same as above. Recommended reading: The rest of Section 5.3 in Dechter. Freuder and Hubbe: A Disjunctive Decomposition Control Schema for Constraint Satisfaction (CP 1993) Peter Cheeseman et al.: Where the Really Hard Problems Are (IJCAI 1991). Sections 5.3.1 and 5.3.2 in Dechter.	Quiz 2

Week 6

Tuesday, Sep 29	Topic: Continuation of CSP 101: Overview: advanced solving techniques and research directions Required reading: Same as above. Recommended reading: Same as above.	Deadline: for project selection. (Use webhandin.) Glossary 3 due Glossary 4 assigned Homework 3 due delayed until Oct 2 Homework 4 assigned
Friday, Oct 2	DB & CSP Required reading: Section 1.3 of Dechter	Homework 3 due

Week 7

Tuesday, Oct 6	Topic: Theoretical Evaluation of BT Algorithms Required reading: A Theorectical Evaluation of Selected Backtracking Algorithms, by Kondrak and van Beek (IJCAI 1995) Recommended reading: Dechter, Chapters 5 and 6	Quiz 3 Glossary 4 due Homework 4 delayed Homework 5 assigned
Friday, Oct 9	Same as above	Glossary 5 assigned

Week 8

Tuesday, Oct 13	Topic: Search Orders in CSPs Required reading: Search Orders in CSPs, Chapter 6, Tsang 93 Recommended reading: Dechter: Sections: 5.1.1 Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen 92	Homework 4 due Homework 5 assigned
Friday, Oct 16	Same as above	Glossary 5 due

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 problems--Mackworth/Freuder Sections 3.1, 3.2, 3.3 of Dechter's book. Recommended reading: Sections 3.4--3.10 of Dechter's book. Networks of Constraints: Fundamental Properties and Application to Picture Processing--Montanari, Information Sciences, 1974. (Retrieve from instructor.) Consistency in networks of relations--Mackworth Constraint propagation with interval labels, E. Davis Path Consistency on Triangulated Constraint Graphs, Bliek, Sam-Haroud, 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

Tuesday, Nov 10	Same as above	Glossary 7 due
Friday, Nov 13	Topic: All-Diff Constraints Required reading: A Filtering Algorithm for Constraints of Differences in CSPs-- Régin, AAAI 1994. Recommended reading: Dechter Chapter 3, entirely.

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 Non-Binary 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 extra-credit work. At most 1 paper presentation, 2 summaries, 1 chapter write-up 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 Coarse-Grained Arc Consistency Algorithm, Christian Bessière et a, Artif. Intell. 165(2): 165-185 (2005).
Friday, Dec 4	Consistency in non-binary CSPs	Deadlines: Final glossary due, in print and using handin. Project reports are due in print and using handin. Second deadline for extra-credit work: No paper presentation, summaries, write-ups, 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