CSCE990-05, Fall 2000: Foundations of Constraint Satisfaction                                                            Main page of the course. 

---

• Administration and background information: Handout 1
• Constraint Satisfaction Problems, An Overview.  Pedro Meseguer
• Constraint Satisfaction,  Rina Dechter.  MIT Encyclopedia of the Cognitive Sciences
• Definition of a join in DB, Kanellakis, Handbook of Theoretical Computer Science
• Steps for proving  a problem NP-complete
• Introduction and highlights: Handout 2
• Glossary I
• Glossary 2
• Glossary 3
• Basic consistency algorithms: Handout 3
• Examples and Riddle 1: Handout 4
• Glossary 4
• Prosser's IC'93 paper
• Hybrid backtracking algorithms:  Handout 5
• Kondrak & van Beek, IJCAI'95
• Theoretical evaluations of backtracking algorithms: Handout 6
• Glossary 5
• Variable, value ordering heuristics: Handout 7, Handout 8
• Tsang Chapter 6; Geelen, ECAI'92
• Glossary 6
• Synthesizing constraint expressions--Freuder'78, Handout 9
• Glossary 7
• Binary vs. non-binary representations of constraint-- Bacchus and Van Beek, 98, Handout 10
• Suggestion Strategies for Constraint-Based Matchmaker Agents-- Freuder and Wallace, Handout by Amy Beckwith
• Backtrack-free search, Backtrack-bounded search-- Freuder'82, Handout 11
• Hierarchical Constraint Satisfaction in Spatial Databases-- Papadias, Kalnis, Mamoulis'99,   Handout by Nimit Mehta
• Glossary 8
• A Filtering Algorithm for Constraints of Differences in CSPs--Régin, AAAI 94), Handout 12
• Summary on local consistency, Handout 13
• Constraint Logic Programming, Handout 14, Handout15 (powerpoint) by Helmut Simonis
• Phase transition, Handout 16
• Disjunctive decomposition schema, Handout 17
• Disjunctive decomposition using CNG sets, and others, Handout 18
• Interchangeability relations, Handout 19

• Aug 21:  Admin & requirements
• Aug 23:  Definition, representation, applications
• Aug 25:  Complexity : characterization, reduction
• Aug 28, 30, Sep 1, 6:  Review of solving techniques, search, 3SAT, quiz1
• Sep 8-15:  Consistency checking, quiz2
• Sep 18-27: Backtracking and consistency checking hybrids, quiz3 and quiz 4, quiz5
• Sep 29, Oct 2,4: Variable, value ordering heuristics, quiz 6
• Oct 6-8:  Constraint synthesis, quiz 7
• Oct 10-12:  Binary/non-binary constraint, quiz 8, quiz 9
• Oct 12-18: Constraint Matchmaker.  (Fall break).
• Oct 19: Backtrack-free search, quiz 10
• Oct 23:  Backtrack-bounded search, quiz 11
• Oct 25-26: Spatial Databases, quiz 12
• Oct 30, Nov 1: class cancelled
• Nov3, 6:  Arc-consistency for all-diff constraints, quiz 13
• Nov 9: Summary on local consistency, intro to CLP, quiz 14
• Nov 13: Talk by Simonis on CLPs
• Nov 15, 17, 20 : phase transtion, quiz 15
• Nov 22, 24: Thanksgiving.
• Nov 27-29: Disjunctive decomposition schema.  Instances: BT, FC, NC, IDC, CPR
• Dec 1: Disjunctive decomposition using CNG-sets,
• Dec 4:  Disjunctive decomposition strategies: mu-BD, FOF, VAD.
• Dec 6, 8: interchangeability relations.
• Dec 12: Project presentations and wrap up session.

Homeworks:

• Homework 1.  Given Fri Sep 1st, 2000, due  Fri Sept 8th, 2000.
• Homework 2.  Given Mon Sep 18th, 2000, due Fri Sep 29th, 2000.
• Homework 3.  Given Mon Oct 2nd, due Mon Oct 9th, 2000. Extended  Wed Oct 11th, 2000.
• Homework 4.  Given Wed Oct 11th, due Fri Oct 20th, 2000. Extended, Mon Oct 23rd, 2000.
• Individual projects.