| Week 1 |
| Mon, Jan 7 |
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 9 |
Topic, required reading, recommended reading: Same as above
|
| Wed, Jan 9 |
Recitation:
Short tutorial on Piazza
Refresher on Handin
About using Grader
Quick review of NP-Completeness (by Shant and Rahul).
|
| Fri, Jan 11 |
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 14
|
| Week 2 |
| Mon, Jan 14 |
Topic, required reading, recommended reading: Same as above.
Announcements:
Take home pretest due
Glossary 1 assigned
|
| Wed, Jan 16 |
Topic, required reading, recommended reading: Same as above.
Announcements:
Homework 1 assigned
Homework 1 Tutorial
|
| Wed, Jan 16 |
Recitation:
Quiz
Homework 1 Tutorial
|
| Fri, Jan 18 |
Topic, required reading, recommended reading: Same as above.
Announcements:
|
| Week 3 |
| Mon, Jan 21 |
Martin Luther King Jr Day (no class)
|
| Wed, Jan 23 |
Topic: Same as above.
Announcement:
Glossary 1 due.
Glossary 2 assigned.
|
| Wed, Jan 23 |
Recitation:
Quiz
|
| Fri, Jan 25 |
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, Jan 28 |
Announcement:
Glossary 2 due.
Glossary 3 assigned.
|
| Wed, Jan 30 |
|
| Wed, Jan 30 |
Recitation:
Quiz
|
| Fri, Feb 1 |
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 4 |
Announcement: None
Glossary 3 due.
Glossary 4 assigned.
|
| Wed, Feb 6 |
Topic: Evaluation of Deterministic Algorithms for CSPs.
Required reading:
Peter Cheeseman et al.: Where the Really Hard Problems
Are (IJCAI 1991).
Additional handout: Protocal for conducting experiments (.jpg)
|
| Wed, Feb 6 |
Recitation:
Quiz
|
| Fri, Feb 8 |
Topic:
Required reading:
Recommended reading:
Announcement:
Homework 2 due
Homework 3 assigned
|
| Week 6 |
| Mon, Feb 11 |
Announcement:
Glossary 4 due.
Glossary 5 assigned.
|
| Wed, Feb 13 |
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 13 |
Recitation:
Quiz
|
| Fri, Feb 15 |
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 18 |
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 20 |
Topic: Same as above.
Required reading: Same as above.
Recommended reading: Same as above.
Announcement: None
|
| Wed, Feb 20 |
Recitation:
Quiz
|
| Fri, Feb 22 |
Announcement:
Homework 3 due
Homework 4 assigned
|
| Week 8 |
| Mon, Feb 25 |
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
|
| Wed, Feb 27 |
Topic: Same as above.
Required reading: Same as above.
Recommended reading: Same as above.
|
| Wed, Feb 27 |
Recitation:
Quiz
|
| Fri, Mar 1 |
Announcements:
List of project distributed
Homework 4 Progress Report due
|
| Week 9 |
| Mon, Mar 4 |
Announcement:
Glossary 7 due
Glossary 8 assigned
|
| Wed, Mar 6 |
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 6 |
Recitation:
Quiz
|
| Fri, Mar 8 |
Announcement:
Homework 4 due
Homework 5 assigned
|
| Week 10 |
| Mon, Mar 11 |
Announcement:
Glossary 9 assigned
|
| Wed, Mar 13 |
Project must be chosen. Submit via handin.
Deadline is 9:00 AM, Tuesday, March 19,
2019. Consult
the
Guidelines for reports.
|
| Wed, Mar 13 |
Recitation:
Quiz
|
| Fri, Mar 15 |
Topic: Local Search
Required reading:
Dechter, Chapter 7
Heuristics
and Stochastic Algorithms (Bartak's online notes)
Recommended reading: <
li> Section 4.3, Chapter 4, AI a Modern Approach (textbook), Russell & Norvig
Stochastic Local Search (book), but Hoos and Stuelze
The Breakout Method for Escaping From Local Minima Paul Morris, AAAI
1993.
Announcement:
Homework 5
Progress Report due 9:00 AM, Tuesday, March 19,
2019
Glossary 9 due
|
| Week 11 |
| Mon, Mar 18 |
Spring Break, no class
|
| Wed, Mar 20 |
| Wed, Mar 20 |
| Fri, Mar 22 |
| Week 12 |
| Mon, Mar 25 |
Announcement:
Homework 5 due
Homework 6 CANCELLED
Homework 6 assigned
Glossary 10 assigned
|
| Wed, Mar 27 |
Topic:Finish Local Search. Start Structure-Based Techniques
Required reading:
Dechter Sections: 2.1.3, 5.1.2, 10.1.1, 4.2.2, 9.2, 4.4, 9.2.2.
Recommended reading:
Tree
Clustering Schemes for Constraint Processing, Dechter and Pearl,
AIJ 1989
Enhancement Schemes for Constraint Processing:
Backjumping, Learning, and Cutset Decomposition (PDF not available
yet), Dechter, AIJ 1990.
Synthesizing constraint expressions, Freuder, JACM 1978
A
Sufficient Condition for Backtrack-Free Search, Freuder, JACM
1982
A
Sufficient Condition for Backtrack-Bounded Search, Freuder, JACM
1985
|
| Wed, Mar 27 |
Recitation:
Quiz
|
| Fri, Mar 29 |
Topic: Same as above
Required reading: Same as above
|
| Week 13 |
| Mon, Apr 1 |
Topic: Same as above
Required reading: Same as above
Announcement:
Glossary 9 due
Homework 6 Progress Report due
|
| Wed, Apr 3 |
Topic: Same as above
Required reading: Same as above
Announcement:
Deadline: Progress reports of projects
are due. (Use handin)
|
| Wed, Apr 3 |
Recitation:
Quiz
|
| Fri, Apr 5 |
Topic: Same as above
Required reading: Same as above
Announcement:
Deadline: First deadline for
extra-credit work. At most 1 paper presentation, 2
summaries, after this date.
|
| Week 14 |
| Mon, Apr 8 |
Topic: Same as above
Required reading: Same as above
Announcements:
Homework 6 due
|
| Wed, Apr 10 |
Topic:Finish: Structure-Based Techniques
Required reading:
Same as above.
|
| Wed, Apr 10 |
Recitation:
Quiz
|
| Fri, Apr 12 |
Topic: More on Consistency Properties
and Algorithms.
Required reading: Refer to slides and
Index of textbook.
|
| Week 15 |
| Mon, Apr 15 |
Topic: Same as above
Required reading: Same as above
|
| Wed, Apr 17 |
Topic: Same as above
Required reading: Same as above
|
| Wed, Apr 17 |
Recitation:
Quiz
|
| Fri, Apr 19 |
Topic: Advanced Backtrack Search
Required reading: Refer to
slides.
Announcements:
Quiz may be given
Deadline: Final glossary due,
in print and using handin.
Deadline: Project report due,
in print and using handin.
Deadline: Second deadline for
extra-credit work: No paper presentation or summaries
after this date.
|
| Week 16 (dead week) |
| Mon, Apr 22 |
Announcements:
PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
|
| Wed, Apr 24 |
Announcements:
PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
|
| Wed, Apr 24 |
Recitation:
PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
|
| Fri, Apr 26 |
Announcements:
PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
Deadline: Project code and slides due,
submit using handin.
Deadline: Final revisions to Project reports are
due in print and using handin.
|
| Week 17 |
| Thu, May 2 |
No Final Examination
7:30—9:30 AM PROJECT DEFENSE. Attendance is mandatory
|