CSCE 421/821

Foundations of Constraint Processing

Detailed Course Schedule

Week 1
Mon, Jan 23 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 25 Topic: CSP 101 (same as above)
    Wed, Jan 25 Recitation: Introduction to CSPs
    Fri, Jan 27 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 30.
    		•
    Week 2
    Mon, Jan 30 Topic, required reading, recommended reading: Same as above.

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

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

    Announcements:
  • Glossary 1 due.
  • Glossary 2 assigned.
  • Homework 1 progress report due
    		•
    Wed, Feb 8 Topic: Same as above.
    Wed, Feb 8 Recitation:
  • Quiz
    • Fri, Feb 10 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 13 Announcement:
  • Glossary 2 due.
  • Glossary 3 assigned.
  • Homework 1 due
  • Homework 2 assigned
    		•
    Wed, Feb 15
    Wed, Feb 15 Recitation:
  • Quiz
    • Fri, Feb 24 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 20 Announcement: None
  • Glossary 3 due.
  • Glossary 4 assigned.
  • Homework 2: progress report due
    		•
    Wed, Feb 22 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 22 Recitation:
  • Quiz
    • Fri, Feb 24 Topic:
    Required reading:
    Recommended reading:
    Announcement:
    Week 6
    Mon, Feb 27 Announcement:
  • Glossary 4 due.
  • Glossary 5 assigned.
  • Homework 2 due
  • Homework 3 assigned
    		•
    Wed, Mar 1 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 1 Recitation:
  • Quiz
    • Fri, Mar 3 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 6 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 8 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.

    Announcement: None
    Wed, Mar 8 Recitation:
  • Quiz
    • Fri, Mar 10 Announcement:
    Mon, Mar 13
    Spring Break, no class
    Wed, Mar 15
    Wed, Mar 15
    Fri, Mar 17
    Week 8
    Week 9
    Mon, Mar 20 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 22 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Wed, Mar 22 Recitation:
  • Quiz
    		•
    Fri, Mar 24
    Announcements:
    Week 10
    Mon, Mar 27
    Announcement:
  • Glossary 7 due
  • Glossary 8 assigned
  • Homework 4: Progress report due
    		•
    Wed, Mar 29 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 29 Recitation:
  • Quiz
    • Fri, Mar 31
    Announcement:
  • First deadline for submitting two paper summaries
    • Week 11
    Mon, Apr 4 Topic:

    Required reading:

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

    Required reading:

    Announcements:
    • Wed, Apr 5 Recitation:
  • Quiz
    • Fri, Apr 7 Topic:

    Required reading:

    Announcements:
    • Week 12
    Mon, Apr 10 Topic:

    Required reading:

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

    Required reading:

    Announcements:
    • Fri, Apr 14 Topic:

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

    Required reading:

    Announcements:
    • Wed, Apr 19 Recitation:
  • Quiz
    • Fri, Apr 21 Topic:

    Required reading:

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

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

    Required reading:

    Announcements:
    Wed, Apr 26 Recitation:
  • Quiz
    • Fri, Apr 28 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, May 1 Topic: Same as above
    Required reading: Same as above

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

    Required reading:

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

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

    Required reading:

    Announcements:
    Week 17 (Finals Week)
    Thu, May 18
    No Final Examination
    7:30—9:30 AM Instructor available for discussion, please drop a message