CSCE 421/821

Foundations of Constraint Processing

Detailed Course Schedule

Week 1
Mon, Jan 13 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 15 Topic, required reading, recommended reading: Same as above
    Wed, Jan 15 Recitation:
  • Short tutorial on Piazza
  • Refresher on Handin
  • About using Grader
  • Quick review of NP-Completeness (by Shant and Rahul).
  • Fri, Jan 17 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 Wednesday, January 22, 2020.
  • Week 2
    Mon, Jan 20
    Martin Luther King Jr Day (no class)
    Wed, Jan 22 Topic, required reading, recommended reading: Same as above.
    Announcements:
  • Take home pretest due
  • Glossary 1 assigned
  • Homework 1 assigned
  • Homework 1 Tutorial
  • Wed, Jan 22 Recitation:
  • Quiz
  • Homework 1 Tutorial
    Fri, Jan 24 Topic, required reading, recommended reading: Same as above.
    Week 3
    Mon, Jan 27 Topic, required reading, recommended reading: Same as above.
    Announcements:
  • Glossary 1 due.
  • Glossary 2 assigned.
  • Wed, Jan 29 Topic: Same as above.
    Wed, Jan 29 Recitation:
  • Quiz
  • Fri, Jan 31 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:
  • Homework 1 due
  • Homework 2 assigned
  • Week 4
    Mon, Feb 3 Announcement:
  • Glossary 2 due.
  • Glossary 3 assigned.
  • Wed, Feb 5
    Wed, Feb 5 Recitation:
  • Quiz
  • Fri, Feb 7 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 10 Announcement: None
  • Glossary 3 due.
  • Glossary 4 assigned.
  • Wed, Feb 12 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 12 Recitation:
  • Quiz
  • Fri, Feb 14 Topic:
    Required reading:
    Recommended reading:
    Announcement:
  • Homework 2 due
  • Homework 3 assigned
  • Week 6
    Mon, Feb 17 Announcement:
  • Glossary 4 due.
  • Glossary 5 assigned.
  • Wed, Feb 19 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 19 Recitation:
  • Quiz
  • Fri, Feb 21 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement:
  • Quiz 3
  • Homework 3 Progress Report due
  • Week 7
    Mon, Feb 24 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 5 due
  • Glossary 6 assigned
  • Wed, Feb 26 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None
    Wed, Feb 26 Recitation:
  • Quiz
  • Fri, Feb 28 Announcement:
  • Homework 3 due
  • Homework 4 assigned
  • Week 8
    Mon, Mar 2 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
  • Wed, Mar 4 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Wed, Mar 4 Recitation:
  • Quiz
  • Fri, Mar 6 Announcements:
  • List of project distributed
  • Homework 4 Progress Report due
  • Week 9
    Mon, Mar 9 Announcement:
  • Glossary 7 assigned
  • Wed, Mar 11 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 11 Recitation:
  • Quiz
  • Fri, Mar 13 Announcement:
  • Homework 4 due
  • Homework 5 assigned
  • Week 10
    Mon, Mar 16
    Classes cancelled
    Wed, Mar 18
    Wed, Mar 18
    Fri, Mar 20
    Week 11
    Mon, Mar 23
    Spring Break, no class
    Wed, Mar 25
    Wed, Mar 25
    Fri, Mar 27
    Week 12
    Mon, Mar 30 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.
  • Wed, Apr 1
    Wed, Apr 1
    Fri, Apr 3
    Week 13
    Mon, Apr 6 Topic: DB vs CSP
    Required reading:Dechter, Section 1.3
    Wed, Apr 8 Same as above
    Wed, Apr 8 Cancelled
    Fri, Apr 10 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

  • Week 14
    Mon, Apr 13 Topic: Same as above
    Required reading: Same as above

    Announcements:
  • Homework 6 due
  • Choose last homework
  • Glossary 9 assigned
  • Practice Quiz
  • Wed, Apr 15 Announcements:
  • Choice of last homework due on Handin
  • Wed, Apr 15
  • Quiz over AllDiff GAC and Relational Algebra
  • Fri, Apr 17
    Week 15
    Mon, Apr 20 Topic:
    Required reading:

    Announcements:
  • Glossary 9 due
  • Glossary 10 assigned
  • Wed, Apr 22 Topic:
    Required reading:

    Announcements:
  • Progress report of last homework due on Handin
  • Wed, Apr 22 Recitation:Quiz
    Fri, Apr 24 Topic:
    Required reading: .
    Week 16 (dead week)
    Mon, Apr 27
    Announcements:
  • Glossary 10 due
  • Wed, Apr 29
    Wed, Apr 29 Recitation:Quiz
    Fri, May 1
    Announcements:
  • Choice of last homework due on Handin
  • Code and (short) report of last homework due
  • Week 17
    Tue, May 5
    No Final Examination
    7:30—9:30 AM Instructor available for discussion, please drop a message