| 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
|