|
Date
|
Material
|
Announcements
|
| Tue, Aug 28 |
Topic: Overview.
Required reading:
Algorithms for Constraint Satisfaction
Problems: A Survey by Vipin Kumar. AI Magazine Sprint 1992.
Recommended reading:
Bartak's on-line guide: Introduction
to CSPs
Constraint
Satisfaction Problems, An Overview. Pedro Meseguer
Constraint
Satisfaction, Rina Dechter. MIT Encyclopedia of the Cognitive
Sciences
Constraint Programming: in Pursuit
of the Holy Grail. Bartak
|
|
| Thu, Aug 30 |
Topic: Overview
Required reading: Bartak's on-line guide: Introduction
to CSPs |
Pretest (20 minutes max). Closed book.
Glossary 1 assigned. |
| Tue, Sep 4 |
Topic: Overview
Required reading: Bartak's on-line guide: Introduction
to CSPs.
Recommended reading:
The Theory of NP-Completeness. Computers and Intractability, Garey &
Johnson (1979), Chapter 2, pages 17--28.
NP-Complete problems. Introduction to Algorithms, Cormen, Leiserson
& Rivest (1990), Section 36.5, pages 946--960.
|
Glossary 1 is due. |
| Thu. Sep 6 |
Project topic must be chosen.
Topic, required reading and recommended reading: same as Sep4 |
Deadline for claiming points for Pretest. |
| Tue, Sep 11 |
Topic: Finish the overview, and Relational Algebra
Required reading:
Notes of Rina Dechter.
Query Algebra Database System Implementation, pages 240--247, Garcia-Molina,
Ullman, Widom. Prentice Hall.
|
WARNING: Last deadline for choosing a project
Homework1 assigned.
Grades of Quiz 1 posted. |
| Thu, Sep 13 |
Topic: Consistency checking
Required reading: The
complexity of some polynomial network consistency algorithms for constraint
satisfaction problems--Mackworth/Freuder
Recommended reading:
Consistency
in networks of relations--Mackworth |
|
| Tue, Sep 18 |
Same as previous. |
Glossary 2 assigned
Quiz 2, grades posted. |
| Thu, Sep 20 |
Same as previous. |
|
| Tue, Sep 25 |
Same as previous. |
Homework 1 is due.
Glossary 2 is due. |
| Thu, Sep 27 |
Same as previous. |
Quiz 3, grades posted. |
| Tue, Oct 2 |
Same as previous. |
Watch out for Quiz 4!
Homewok2 is assiigned
Glossary 3 is assigned |
| Thu, Oct 4 |
Same as previous. |
|
| Tue, Oct 9 |
Topic: Backtracting algorithms
Required reading: Hybrid
algorithms for the constraint satisfaction problem--Prosser
Recommended reading: Tsang, Chapter 5. |
Glossary 3 is due. |
| Thu, Oct 11 |
Same as previous. |
Glossary 4 assigned.
Watch for quiz 5. |
| Tue, Oct 16 |
Progress report on projects are due.
Same as previous. |
Homework 2 is due by 9:30 am. Use Handin.
Solutions to HWK1 available.
(MSWord document) |
| Thu, Oct 18 |
Topic: Theoretical evaluation of backtracking algorithms.
Required reading: A Theoretical Evaluation of Selectted Backtracking
Algorithms. Kondrak and van Beek.
Recommended reading: Determining
if (FC-) (conflict-directed) backjumping visits a given node is NP-hard
, Bernd S.W. Schröder (JUST PUBLISHED). |
Glossary 4 due.
Quiz 6. |
| Tue, Oct 23 |
Fall Semester Break
|
|
| Thu, Oct 25 |
finish previous discussion then..
Topic: Ordering heuristics
Required reading:
Ordering heuristics in CSPs, Tsang
Dual Viewpoint
Heuristics for Binary Constraint Satisfaction Problems, Geelen 92
Recommended reading: |
Glossary 5 assigned.
Homework3
assigned. |
| Tue, Oct 30 |
Same as previous. |
Quiz 7 |
| Thu, Nov 1 |
Same as previous. |
Practice talk by Rob Glaubius
Glossary 5 due.
Corrections to HWK2 distributed on paper |
| Tue, Nov 6 |
Topic: Constraint synthesis
Required reading:
Synthesizing
constraint expressions--Freuder'78
Tsang, Sections 9.1 & 9.2
Recommended reading: |
|
| Thu, Nov 8 |
Topic: Reduction from non-binary to binary CSPs
Required reading: Binary vs.
non-binary representations of constraint-- Bacchus and Van Beek, 98,
F. Bacchus and P. van Beek, National Conference on Artificial Intelligence
(AAAI-98), pages 311-318, 1998.
Recommended reading:
"On forward checking for non-binary constraint
satisfaction" C. Bessière and P. Meseguer and E.C. Freuder and
J. Larrosa, Proceedings CP'99, Alexandria VA, pages 88-102.
Decomposable Constraints.
Ian Gent, Kostas Stergiou and Toby Walsh. Artificial Intelligence, 123
(1-2), 133-156, 2000.
|
Homework3 due.
HWK3: Extension until Monday
Nov 12, 2001. 9:30 am.
|
| Tue, Nov 13 |
Same as above |
|
| Thu, Nov 15 |
Same as above |
|
| Tue, Nov 20 |
Topic: Backtrack-free and backtrack-bounded search
Required reading: 2 papers by Freuder
Recommended reading: |
Bonus quiz: Quiz 9 |
| Thu, Nov 22 |
Thanksgiving vacation
|
|
| Tue, Nov 27 |
Visitor: Dr. Brian Drabble
Talk: Constraint-Based
Scheduling and Optimization: From Research to Application.
Speaker's slides (soon).
Recommended reading:
Dymanic Schedule Management: Lessons
from the Air Campaign Planning Domain, Drabble & Haq, Europear
Conference on Planning (ECP'01).
Can Search Play A Role in Practical
Applications? Ginsberg, Etherington, Drabble. AI Meets the World,
1998.
More papers from CIRL: ftp://ftp.cirl.uoregon.edu/pub/users/ether/README.html |
Please confirm to instructor if you are joining the class for lunch
with Dr. Drabble. |
| Thu, Nov 29 |
Topic: Phase transition
Required reading: Where
the really hard problems are (Cheeseman et al. 1991)
Recommended reading:
The
authors page about this paper
Hays (American Scientist 97) `Can't
get No Satisfaction' (less technical.)
Gent et al. (APES-TR 12-1999) `Constrainedness
of Search.'
Gent et al. (APES-TR 08-1998) `Random
Constraint Satisfaction: Flaws and Structure.'
Gent et al. (APES-TR 97): `How
not to do it.'
|
Homework 4 assigned.
The discussion of the topic listed under Nov 20th is delayed until
we have covered phase transition. |
| Tue, Dec 4 |
Topic: Genetic threading,
presentation by Alexander Tchourbanov
Required reading: Genetic threading, paper by Yadgary &Amir
Recommended reading: |
|
| Thu, Dec 6 |
Topic:
Backtrack-free search
Project presentation Buettner/Lueninghoener.
|
`Homework 4 due. |
| Tue, Dec 11 |
Dead week. Project presentations, final
reports due.
Presentations given: Zou, Guddetti, Xu, Chen /Yap, Kavan. |
|
| Thu, Dec 13 |
Dead week. Project presentations, final
reports due. |
You must return before 12:00 pm:
Paper: (1) your type-written report and (2) printed code.
Tar'red file: (1) slides of your presentation, (2) report, (3) code.
Your final, global glossary (when applicable). Printed form.
Class
will be held in Room 114 in Ferguson.
and will start at 9:00 a.m.
|
| Fri, Dec 21 |
No final exam. (otherwise scheduled between 10:00 and 12:00)
|
|