Detailed Course Schedule

Week 1

Tuesday, Aug 25	Administrivia	Syllabus, Guidelines, Topics
Thursday, Aug 27	Temporal Reasoning	Dechter's Chapter 12
Actions:	Shant: Prepare [Choueiry & Xu, 2005] Chris: Check [Liu, Li, Renz, 2009] Robert: Check O(n^3) in [Allen, 1983] Wesley: Check [Koubarakis, 1997] (PDF, PS)

Week 2

Tuesday, Sep 2	Same as above.	Will try to address your questions
Thursday, Sep 4	Same as above	Quiz 1

Week 3

Tuesday, Sep 8	Finish Chapter 12
Thursday, Sep 10	More on Temporal Reasoning Speaker: Shant (Triangle-AC) Scribe: Robert (Notes)	Quiz 2 Triangle-AC by Choueiry and Xu Triangle-STP by Xu and Choueiry TCSP by Xu and Choueiry

Week 4

Tue, Sep 15	Introduction Constraint Databases	Guest Lecturer: Dr. Revesz
Thu, Sep 17	No Class	Instructor out of town

Week 5

Tuesday, Sep 22	Row-Convexity	van Beek, P., and Dechter, R., "On The Minimality And Global Consistency Of Row-Convex Constraint Networks." Journal of the ACM, Vol. 42, No. 3, May 1995, pp. 543-561. Dechter, Section 8.5, pages 231--237 Bessiere et al. "Making Bound Consistency as Effictive as Arc Consistency," IJCAI 2009, pages 425--430
Thursday, Sep 24	Same as above.	Same as above.

Week 6

Tuesday, Sep 29	Same as above.	Same as above.
Thursday, Oct 1	Tree Clustering and Adaptive Consistency Speakers: Chris Reeson (Tree Clustering) and Peter (Computing Cliques and Join Trees) Scribe: Pingyu (Notes).	Dechter, R. and Pearl, J. "Tree Clustering for Constraint Networks." Artificial Intelligence (38), 1989, pp. 353-366.

Week 7

Tuesday, Oct 6	Interchangeability	Freuder, E.C. Eliminating Interchangeable Values in Constraint Satisfaction Problems
Thursday, Oct 8	Interchangeability and Bundling (PS) Dynamic Bundling in CSPs Going through your questions	Quiz 2 finally Haselboeck: Exploiting Interchangeabilities in Constraint Satisfaction Problems, IJCAI 1993 Choueiry and Davis: Dynamic Bundling: Less Effort for More Solutions, SARA 2002 Lal et al.: Neighborhood Interchangeability and Dynamic Bundling for Non-Binary Finite CSPs , AAAI 2005

Week 8

Tuesday, Oct 13	Interchangeability and Insterchange in Search (bundling) PS document, sorry Dynamic Bundling in CSPs Going through your questions	Quiz 2 finally, 3 hopefully.. Same as above.
Thursday, Oct 15	Topic: Solution Counting Speaker: Shant (Sol Counting) Scribe: Chris (Notes).	Favier et al. Exploiting Problem Structure for Solution Counting, CP 2009

Week 9

Tuesday, Oct 20	No class	Fall Break
Thursday, Oct 22	Theorem 5 of [Freuder AAAI91] Application in Geospatial Reasoning	Bayer et al. Reformulating CSPs for Scalability with Application to Geospatial Reasoning

Week 10

Tuesday, Oct 27	BID problem	Same as above
Thursday, Oct 29	Topic: P3C, triangle-STP, PC Speakers: Peter and Wesley (PPT) Scribe: Shant (Notes)	Optional midterm due P3C Planken et al. Triangle-STP , Xu and Choueiry PPC, Bliek and Sam-Haroud

Week 11

Tuesday, Nov 3	Same as above	Same as above
Thursday, Nov 5	Same as above	Same as above

Week 12

Topic:

Discussion.

Tuesday, Nov 10	Topic: Tree Convex Constraints Speaker: Robert (PTTX) Scribe: Peter (Notes)	Properties of Tree Convex Constraints, Zhang and Freuder
Thursday, Nov 12

Week 13

Tuesday, Nov 17	Topic: Rectangle Packing Speaker: Chris (PPTX) Scribe: Robert (Notes)	Optimal Rectangle Packing: A Meta-CSP Approach
Thursday, Nov 19	Topic: Covering Arrays Speaker: Pingyu (PPTX) Scribe: Wesley (Notes)	Constraint Models for the Covering Test Problem, Hnich et al. Homework 1 (PDF) assigned

Week 14

Tuesday, Nov 24	Pingyu will finish his talk. Topic: Structure in SAT Speaker: Chris (PPTX) Scribe: Shant (Notes)	Required reading: Building Structure into Local Search for SAT, Pham et al., IJCAI 07 Recommended reading: Recovering and Exploiting Structural Knowledge from CNF Formulas, Ostrowski et al., CP 2002
Thursday, Nov 26	No Class - Thanksgiving Break

Week 15

Tuesday, Dec 1	Topic: SAT and CP Speaker: Pingyu Scribe: Wesley (Notes)	Propositional Satisfiability and Constraint Programming: A Comparative Survey, Bordeaux et al., ACM Computing Surverys 2006 Homework 1 (PDF) due
Thursday, Dec 3	Topic: Same as above Speaker: Pingyu, Part II Scribe: Chris (Notes, Part II)

Week 16 - Dead Week

Tuesay, Dec 8	Cancelled for inclement weather
Thursday, Dec 10	Same as above (finishing discussion) Discussion of residues (useful for search w/ lookahead) Basic Algebra for Symmetry by Robert	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 Bessiere et al., Artif. Intell. 165(2): 165-185 (2005). Chapter 10 from Handbook of CP

Week 17 - Finals Week

Friday, Dec 18