CSCE 421/821

Foundations of Constraint Processing

Detailed Course Schedule

Week 1
Mon, Jan 17 Martin Luther King Day
Wed, Jan 19 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 19 Recitation: Introduction to CSPs
    Fri, Jan 21 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, Jan 24.
    		•
    Week 2
    Mon, Jan 24 Topic, required reading, recommended reading: Same as above.

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

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

    Announcements:
  • Glossary 1 due.
  • Glossary 2 assigned.
  • Homework 1 progress report due
    		•
    Wed, Feb 2 Topic: Same as above.
    Wed, Feb 2 Recitation:
  • Quiz
    • Fri, Feb 4 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 7 Announcement:
  • Glossary 2 due.
  • Glossary 3 assigned.
  • Homework 1 due
  • Homework 2 assigned
    		•
    Wed, Feb 9
    Wed, Feb 9 Recitation:
  • Quiz
    • Fri, Feb 11 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 14 Announcement: None
  • Glossary 3 due.
  • Glossary 4 assigned.
  • Homework 2: progress report due
    		•
    Wed, Feb 16 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 16 Recitation:
  • Quiz
    • Fri, Feb 18 Topic:
    Required reading:
    Recommended reading:
    Announcement:
    Week 6
    Mon, Feb 21 Announcement:
  • Glossary 4 due.
  • Glossary 5 assigned.
  • Homework 2 due
  • Homework 3 assigned
    		•
    Wed, Feb 23 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, Feb 23 Recitation:
  • Quiz
    • Fri, Feb 25 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.

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

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

    Announcement: None
    Wed, Mar 2 Recitation:
  • Quiz
    • Fri, Mar 4 Announcement:
    Week 8
    Mon, Mar 7 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:
  • Glossary 6 due
  • Glossary 7 assigned
  • Homework 3 due
  • Homework 4 assigned
    		•
    Wed, Mar 9 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Wed, Mar 9 Recitation:
  • Quiz
    		•
    Fri, Mar 11
    Announcements:
    Week 9
    Mon, Mar 13
    Spring Break, no class
    Wed, Mar 15
    Wed, Mar 15
    Fri, Mar 17
    Week 10
    Mon, Mar 21
    Announcement:
  • Glossary 7 due
  • Glossary 8 assigned
  • Homework 4: Progress report due
    		•
    Wed, Mar 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

    		•
    Wed, Mar 23 Recitation:
  • Quiz
    • Fri, Mar 25
    Announcement:
  • First deadline for submitting two paper summaries
    • Week 11
    Mon, Mar 28 Topic:

    Required reading:

    Announcements:
  • Homework 4 due
  • Homework 5 assigned
  • Glossaries will be resynchronized with lecture given progress
    • Wed, Mar 30 Topic:

    Required reading:

    Announcements:
    • Wed, Mar 30 Recitation:
  • Quiz
    • Fri, Apr 1 Topic:

    Required reading:

    Announcements:
    • Week 12
    Mon, Apr 4 Topic:

    Required reading:

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

    Required reading:

    Announcements:
    • Fri, Apr 8 Topic:

    Required reading:
    • Week 13
    Mon, Apr 11 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 13 Topic:

    Required reading:

    Announcements:
    • Wed, Apr 13 Recitation:
  • Quiz
    • Fri, Apr 15 Topic:

    Required reading:

    Announcements:
    • Week 14
    Mon, Apr 18 Topic:
    Required reading:

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

    Required reading:

    Announcements:
    Wed, Apr 20 Recitation:
  • Quiz
    • Fri, Apr 22 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 15
    Mon, Apr 25 Topic: Same as above
    Required reading: Same as above

    Announcements:
  • Homework 6 due
    		•
    Wed, Apr 27 Announcements:
    Wed, Apr 27
  • Quiz
    • Fri, Apr 29 Topic:

    Required reading:

    Announcements:
    Week 16 ( Week)
    Mon, May 2 Topic: Same as above
    Required reading: Same as above

    Announcements:
  • Homework 6 due
    		•
    Wed, May 4 Announcements:
    Wed, May 4
  • Quiz
    • Fri, May 6 Topic:

    Required reading:

    Announcements:
    Week 17 (Finals Week)
    Wed, May 11
    No Final Examination