CSCE 421/821

Foundations of Constraint Processing

Detailed Course Schedule

Week 1
Mon, Jan 25 Class cancelled for inclement weather
Wed, Jan 27 Topic: Rules of the game
  • Course syllabus (distributed)
  • Administrative rules including deadlines
  • Guidelines for reports

    • Topic: CSP 101, Overview
  • Instructor's slides: Constraint Processing 101 (PPTX)

    • 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 (PDF) Bartak

    • Recommended reading:
  • Bartak's on-line guide: Introduction to CSPs
  • Constraint Satisfaction (PDF) Rina Dechter. MIT Encyclopedia of the Cognitive Sciences 
  • Systematic Search Algorithms, Bartak's online notes
  • Heuristics and Stochastic Algorithms, Bartak's online notes
    • Wed, Jan 27 Recitation: Introduction to CSPs
    Fri, Jan 29 Topic: CSP 101 (same as above)

    Pretest:
  • In-class: closed book, handwritten crib sheet allowed, must be turned in with test
  • Take-home: collaboration, discussion strictly forbidden. Due Monday, Feb 1.
    		•
    Week 2
    Mon, Feb 1 Topic, required reading, recommended reading: Same as above.

    Announcements:
  • Take home pretest due
  • Glossary 1 assigned
  • Homework 1 assigned
  • Homework 1 Tutorial
    		•
    Wed, Feb 3 Topic, required reading, recommended reading: Same as above.

    Announcements:
  • Take home pretest due
  • Glossary 1 assigned
  • Homework 1 assigned
  • Homework 1 Tutorial
    		•
    Wed, Feb 3 Recitation:
  • Quiz
  • Homework 1 Tutorial
  • Short tutorial on Piazza
  • Refresher on Handin
  • Quick review of NP-Completeness (by Shant and Rahul).
    		•
    Fri, Feb 5 Topic, required reading, recommended reading: Same as above.
    Week 3
    Mon, Feb 8 Topic, required reading, recommended reading: Same as above.

    Announcements:
  • Glossary 2 assigned.
  • Homework 1 progress report due
    		•
    Wed, Feb 10 Topic: Same as above.
    Wed, Feb 10 Recitation:
  • Quiz
    • Fri, Feb 12 Topic: Arc Consistency: AC-1, AC-3, AC-4.

    Required reading:
  • Section 3.1 and 3.2 in Chapter 3 of Dechter
  • The complexity of some polynomial network consistency algorithms for constraint satisfaction problems Mackworth & Freuder, AIJ 1985 (only AC algorithms)

    • Recommended reading:
  • Consistency Techniques (Bartak's online notes)
  • Paper on AC4: Arc and Path Consistency Revisited (PDF) Mohr and Henderson, AIJ 1986
  • Paper on AC3.1/2001: An Optial Coarse-Grained Arc Consistency Algorithm (PDF) Bessiere et al., AIJ 2005

    • Announcement:
    Week 4
    Mon, Feb 15 Announcement:
  • Glossary 3 assigned.
  • Homework 1 due
  • Homework 2 assigned
    		•
    Wed, Feb 17
    Wed, Feb 17 Recitation:
  • Quiz
    • Fri, Feb 19 Topic: Finish AC; Start Backtracking Search.

    Required reading:
  • Hybrid algorithms for the constraint satisfaction problem (PDF) Prosser

    • Recommended reading:
  • Chapters 5 and 6, Dechter
  • Chapter 5, Tsang

    • Announcement:
  • Homework 2 Progress Report due
    		•
    Week 5
    Mon, Feb 22 Announcement: None
  • Glossary 4 assigned.
  • Homework 2: progress report due
    		•
    Wed, Feb 24 Topic: Evaluation of Deterministic Algorithms for CSPs.

    Required reading:
  • Peter Cheeseman et al.: Where the Really Hard Problems Are (IJCAI 1991).

    • Additional handout: Protocol for conducting experiments (.jpg)
    Wed, Feb 24 Recitation:
  • Quiz
    • Fri, Feb 26 Topic:
    Required reading:
    Recommended reading:
    Announcement:
    Week 6
    Mon, Mar 1 Announcement:
  • Glossary 5 assigned.
  • Homework 2 due
  • Homework 3 assigned
    		•
    Wed, Mar 3 Topic: Forward Checking. Start theoretical evaluation.

    Required reading:
  • A Theorectical Evaluation of Selected Backtracking Algorithms, by Kondrak and van Beek (IJCAI 1995)

    • Recommended reading:
  • Dechter, Chapters 5 and 6

    • Wed, Mar 3 Recitation:
  • Quiz
    • Fri, Mar 5 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.

    Announcement:
  • Quiz
  • Homework 3 Progress Report due
    		•
    Week 7
    Mon, Mar 8 Topic: Search Orders in CSPs. Required reading:
  • Chapter 6, Tsang 93
    • Recommended reading:
  • Dechter: Sections: 5.1.1
  • Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen ECAI 92

    • Announcement:
  • Glossary 6 assigned
  • Homework 3: progress report due
    		•
    Wed, Mar 10 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.

    Announcement: None
    Wed, Mar 10 Recitation:
  • Quiz
    • Fri, Mar 12 Announcement:
    Week 8
    Mon, Mar 15 Topic: GAC on AllDiff Constraint.
    Required reading:
  • Régin (AAAI 94): A Filtering Algorithm for Constraints of Differences in CSPs.
  • Dechter, Section 3.5.1.
    • Recommended reading:
  • An N^{5/2} Algorithm for Maximum Matchings in Bipartite Graphs, Hopcroft and Karp, SIAM Journal on Computing, Vol 2, No 4, December 1973.
  • Check the literature for recent developments on All-Diff constraint and other global constraints.

    • Announcement:
  • Homework 3 due
  • Homework 4 assigned
    		•
    Wed, Mar 17 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Wed, Mar 17 Recitation:
  • Quiz
    		•
    Fri, Mar 19
    Announcements:
    Week 9
    Mon, Mar 22
    Announcement:
  • Glossary 7 assigned
  • Homework 4: Progress report due
    		•
    Wed, Mar 24 Topic: Path Consistency.
    Required reading:
  • The complexity of some polynomial network consistency algorithms for constraint satisfaction problems Mackworth & Freuder, AIJ 1985 (only AC algorithms)
  • Dechter: Sections 3.1, 3.2, 3.3.
    • Recommended reading:
  • Consistency Techniques (Bartak's online notes)
  • Chapter 3 entirely
  • Path Consistency on Triangulated Constraint Graphs , Bliek and Haroud

    		•
    Wed, Mar 24 Recitation:
  • Quiz
    • Fri, Mar 26
    Announcement:
  • First deadline for submitting two paper summaries
    • Week 10
    Mon, Mar 29 Topic:

    Required reading:

    Announcements:
  • Homework 4 due
  • Homework 5 assigned
    		•
    Wed, Mar 31 Topic:

    Required reading:

    Announcements:
    • Wed, Mar 31 Recitation:
  • Quiz
    • Fri, Apr 2 Topic:

    Required reading:

    Announcements:
    • Week 11
    Mon, Apr 5 Topic:

    Required reading:

    Announcements:
  • Homework 5: Progress report due
    		•
    Wed, Apr 7 Recitation:
  • Quiz
    • Wed, Apr 7 Topic:

    Required reading:

    Announcements:
    • Fri, Apr 9 Topic:

    Required reading:
    • Week 12
    Mon, Apr 12 Topic: GAC on AllDiff Constraint.
    Required reading:
  • Régin (AAAI 94): A Filtering Algorithm for Constraints of Differences in CSPs.
  • Dechter, Section 3.5.1.
    • Recommended reading:
  • An N^{5/2} Algorithm for Maximum Matchings in Bipartite Graphs, Hopcroft and Karp, SIAM Journal on Computing, Vol 2, No 4, December 1973.
  • Check the literature for recent developments on All-Diff constraint and other global constraints.

    • Announcements:
  • Homework 5 due
  • Homework 6 assigned
    		•
    Wed, Apr 14 Topic:

    Required reading:

    Announcements:
    • Wed, Apr 14 Recitation:
  • Quiz
    • Fri, Apr 16 Topic:

    Required reading:

    Announcements:
    • Week 13
    Mon, Apr 19 Topic:
    Required reading:

    Announcement:
  • Homework 6: Progress report due
    		•
    Wed, Apr 21 Topic:

    Required reading:

    Announcements:
    Wed, Apr 21 Recitation:
  • Quiz
    • Fri, Apr 23 Topic: Path Consistency.
    Required reading:
  • The complexity of some polynomial network consistency algorithms for constraint satisfaction problems Mackworth & Freuder, AIJ 1985 (only AC algorithms)
  • Dechter: Sections 3.1, 3.2, 3.3.
    • Recommended reading:
  • Consistency Techniques (Bartak's online notes)
  • Chapter 3 entirely
  • Path Consistency on Triangulated Constraint Graphs , Bliek and Haroud


    • Announcements:
  • Second deadline for submitting two paper summaries
    • Week 14
    Mon, Apr 26 Topic: Same as above
    Required reading: Same as above

    Announcements:
  • Glossary 9 assigned
  • Homework 6 due
    		•
    Wed, Apr 28 Announcements:
    Wed, Apr 28
  • Quiz
    • Fri, Apr 30 Topic:

    Required reading:

    Announcements:
    Week 15
    Thu, May 6
    No Final Examination
    7:30—9:30 AM Instructor available for discussion, please drop a message