CCSCE421/821, Fall 2004: Foundations of Constraint Processing                                                             Main page of the course.  

---

• CP On Line.

• Kye Halsted: Scramble Squares Puzzle as a CSP.

• Constraint Processing:
• Kai Wen Ham: Tsang's textbook online
• Nurzhan Ustemirov: De Schreye's notes  (MSword notes, Power point slides1, slides2) from his Intro to AI Course
• AI resources:
• Ryan Lim: CMU AI Repository
• Latex resources
• Joel Gompert: Getting memory-efficient, pretty-looking, robust graphics with very fancy robust labels into LaTeX
• Ryan Lim: The not so short introduction to LaTex2x
• LISP resources
• Eric Moss: Screamer
• Eric Moss' personal help with Lisp
• Eric Moss:  There is a new Common Lisp implementation on the market (beta copy at this point).  It's supposedly good for multiprocessor systems that need multi-threaded apps using real OS threads.

• Chris Hammack: a really cool Java Applet: Consistency Based CSP Solver. 

List of projects:

1. Todd Blank: CSP encodings for SAT.
2. L.D. Miller: Evaluation of Geelen's promise heuristics.
3. Jose Robayo-Bargans: Constrained-Based Scheduling
4. Yang Shi
5. Mythri Telakapalli: Evaluation of IDC decomposition
6. Shashu Wu: All-diff constraint filtering
7. Mark Baker: none
8. Russell Kearn and Matt Mueller: Forward checking in non-binary CSPs.
9. Guashan Yu: RAIN

Homework:
You must submit your files via handin when required

Homework	Date assigned	Due Date
Homework 1 (ps, pdf)	Friday, Sep 3, 2004	Monday, Sep 13, 2004 Submit by pen+paper or print out right before class
Homework 2 (ps, pdf)	Wed, Sep 15, 2004	Friday, Sep 24, 2004. Extension till Monday Sep 27.
Homework 3 (ps, pdf)	Friday Sep 24, 2004	Friday, October 8, 2004.
Homework 4 (ps, pdf)	October 15th, 2004	November 1st, 2004.
Homework 5 (ps, pdf)	November 8th, 2004	November 22nd, 2004.

Glossaries:

1. Glossary 1
2. Glossary 2
3. Glossary 3
4. Glossary 4
5. Glossary 5
6. Glossary 6

Handouts:

1. Syllabus and grading strategy
2. Administrative Note (powerpoint)
3. Guidelines for reports (powerpoint)
4. Constraint Processing 101 (powerpoint)
5. Backtracking mechanims (powerpoint)
6. List of projects (ps, ps)
7. Overview: advanced solving techniques and research directions (powerpoint)
8. An Interactive System for Hiring and Managing Graduate Teaching Assistants (powerpoint) by Ryan Lim
9. An Improved Restart Strategy for Randomized Backtrack Search (powerpoint) by Praveen Venkata Guddeti
10. Interchangeability in CSPs (powerpoint) by Anagh Lal
11. A Theorectical Evaluation of Selected Backtracking Algorithms, by Kondrak and van Beek
12. Instructor's slides: A Theorectical Evaluation of Selected Backtracking Search (powerpoint)
13. Instructor's slides: Constraints & Relational Databases (powerpoint)
14. Instructor's slides: Consistency: Main Properties and Algorithms for Achieving them (powerpoint)
15. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems--Mackworth/Freuder
16. " Planning in Interplanetary Space: Theory and Practice." Ari Jonsson, Paul Morris, Nicola Muscettola, Kanna Rajan and Ben Smith. In the Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling, 2000
17. Slides of Dr. Jeremy Frank: Constraint Reasoning in Zero Gravity (pdf file)
18. Search Orders in CSPs (powerpoint)
19. Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen (ECAI 92)
20. Instructor's slides: Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems (ps, pdf)
21. Instructor's slides: Advanced Backtrack Search (powerpoint slides).
22. Instructor's slides: Local Search (powerpoint slides).
23. Frequency Assignment for Cellular Mobile Systems Using Constraint Satisfaction Techniques. Makoto Yokoo and Katsutoshi Hirayama IEEE Annual Vehicular Technology Conference (VTC2000-Spring), pp. 888--894, 2000.
24. Mythri's slides: Frequency Assignment for Cellular Mobile Systems Using Constraint Satisfaction Techniques (powerpoint slides).

Material discussed during recitation:

Schedule:
 

Date	Material	Announcements
Mon, Aug 23	Topic: Administrative rules.	Instructor out of town. Handouts distributed: syllabus, (tentative) schedule, administrative rules, guidelines for reports
Wed, Aug 25	Topic:  Administrative rules (if not finished on Monday)	Instructor out of town.
Wed, Aug 25	Recitation cancelled	Instructor out of town.
Fri, Aug 27	Pretest:   In class (closed book) Take home (individual effort, no collaboration)	Instructor out of town.
Mon, Aug 30	Topic:   Introductions to CSP Required reading: Algorithms for Constraint Satisfaction Problems: A Survey by Vipin Kumar. AI Magazine Spring 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
Wed, Sep 1	Topic:   CSP 101 Required reading: Same as above  Recommended reading: Same as above	Joel Gompert (jgompert@cse.unl.edu), RA at the Constraint Systems Laboratory, will be holding office hours every Monday, from 5:00 pm to 6:00 pm in his office in Avery 123D.
Wed, Sep 1	Make-up class  from 5:00 p.m. to 6:00 p.m. Pretest correction. Topic: CSP 101 Required reading:   Same as above. Recommended reading:   Same as above.
Fri, Sep 3	Topic: CSP 101 Required reading:   Same as above Recommended reading:  Same as above	Quiz 1 Glossary 1 assigned Homework 1 assigned
Mon, Sep 6	Labor day
Wed, Sep 8	Topic:   Required reading:   Recommended reading:	Glossary 1 due
Wed, Sep 8	Make-up class or Recitation from 5:00 p.m. to 6:00 p.m.
Fri, Sep 10	Academic visitor:  Professor Ruzena Bajcsy
Mon, Sep 13	Topic:   Backtracking Required reading:   Hybrid algorithms for the constraint satisfaction problem--Prosser Recommended reading:   Chapter 5, Tsang Chapters 5 and 6, Dechter Lecture notes of Fahiem Bacchus: Chapter 2, Section 2.4 (available upon demand) Lecture notes of Pandu Nayad: Handouts 4 & 5	Homework 1
Wed, Sep 15	Topic:   Hybrids of Backtrack Search Required reading:   same as above Recommended reading: same as above	Alert: Quiz 2 Glossary 2 assigned HWK2 assigned List of projects is now available (ps, ps)
Wed, Sep 15	Make-up class  from 5:00 p.m. to 6:00 p.m. Topic:   Hybrids of Backtrack Search Required reading:   same as above Recommended reading:   same as above	Progressing with lecture Correction of pretest (take home) Correction of quiz Discussion of new homework
Fri, Sep 17	Topic:   Hybrid BT Required reading:   same as above Recommended reading:   same as above
Mon, Sep 20	Topic:   Hybrid BT Required reading:   same as above Recommended reading: same as above	Glossary 2 due
Wed, Sep 22	Topic:   Hybrid BT Required reading:   same as above Recommended reading: same as above	Quiz 3 Glossary 3 assigned
Wed, Sep 22	Make-up class  from 5:00 p.m. to 6:00 p.m.	Progressing with lecture Correction of quiz Quick introduction to lex/yacc by Joel Gompert Discussion of new homework
Fri, Sep 24	Topic:   Overview: Advanced solving techniques and research directions. Required reading:   None Recommended reading:   See items listed for Mon, Aug 23.	HWK3 assigned HWK2 extended until Monday Sep 29
Mon, Sep 27	Ryan Lim will discuss GTAAP Recommended reading: `An Interactive System for Hiring and Managing Graduate Teaching Assistants,' Ryan Lim, Venkata Praveen Guddeti, and Berthe Y. Choueiry. (ps, pdf)	HWK2 extended until Monday Sep 29 Yaling Zheng (GTA), Instructor, and Joel Gompert (RA) out of town, office hours cancelled. Glossary 3 due
Wed, Sep 29	Praveen Guddeti will discuss randomized BT search in GTAAP Recommended reading: `An Improved Restart Strategy for Randomized Backtrack Search,' Venkata Praveen Guddeti and Berthe Y. Choueiry (ps, pdf)	Quiz 4 GTA, RA, and instructor out of town
Wed, Sep 29	Recitation cancelled	GTA, RA, and instructor out of town
Fri, Oct 1	Anagh Lal will discuss symmetry detection and bundling Recommended reading: `Neighborhood Interchangeability and Dynamic Bundling for Non-Binary Finite CSPs,' Anagh Lal, Berthe Y. Choueiry, and Eugene C. Freuder, (ps, pdf)	GTA, RA, and instructor out of town
Mon, Oct 4	Topic: Backtracking: A Theoretical Approach Required reading:   A Theorectical Evaluation of Selected Backtracking Algorithms Recommended reading:   The longer and improved paper, which appeared in the AIJ	Deadline for project selection (use handin)
Wed, Oct 6	Topic:   Backtracking: A Theoretical Approach Required reading:   Same as above Recommended reading:   Same as above
Wed, Oct 6	Make-up class  from 5:00 p.m. to 6:00 p.m. Topic:   Same as above Required reading:   Same as above Recommended reading:   Same as above
Fri, Oct 8	Class cancelled	HWK3 due Instructor out of town
Mon, Oct 11	Topic:   Using Independent Sets to Decompose CSPS, Joel Gompert Required reading:   AIMA (textbook of 476/876), Section 5.4, page 151. Recommended reading:   Local Search With Maximal Independent Sets (gzipped ps , pdf)	Instructor out of town
Wed, Oct 13	Topic:   Structural Decomposition Techniques for CSPs, Yaling Zheng Required reading:   Recommended reading:   New Structural Decomposition Techniques for Constraint Satisfaction Problems (ps , pdf)	Quiz 5 (looong) Instructor out of town
Wed, Oct 13	Recitation cancelled	Instructor out of town
Fri, Oct 15	Topic:   Constraints & Relational Databases Required reading:   Dechter's book, Section 1.3. Recommended reading:   Query Algebra Database System Implementation, pages 240--247, Garcia-Molina, Ullman, Widom. Prentice Hall.	HWK4 assigned
Mon, Oct 18	Fall break
Wed, Oct 20	Topic:   Same as above Required reading:   Same as above Recommended reading: Same as above
Wed, Oct 20	Make-up class from 5:00 p.m. to 6:00 p.m. Topic:   Consistency Algorithms Required reading: Sections 3.1, 3.2, 3.3 of Dechter's book. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems--Mackworth/Freuder Recommended reading:  Sections 3.4--3.10 of Dechter's book. Networks of Constraints: Fundamental Properties and Application to Picture Processing--Montanari, Information Sciences, 1974. (Retrieve from instructor.) Consistency in networks of relations--Mackworth Constraint propagation with interval labels, E. Davis Path Consistency on Triangulated Constraint Graphs, Bliek, Sam-Haroud, IJCAI 99	Glossary 4 assigned
Fri, Oct 22	Topic:   Same as above Required reading:   Same as above Recommended reading:   Same as above
Mon, Oct 25	Topic:   Same as above (AC-1, AC-3, AC-4) Required reading:   Same as above Recommended reading:   Same as above	Glossary 4 due
Wed, Oct 27	Topic:   Same as above Required reading:   Same as above Recommended reading:   Same as above
Wed, Oct 27	Make-up class from 5:00 p.m. to 6:00 p.m. Topic:   Path Consistency Required reading:   Same as above Recommended reading:   Same as above
Fri, Oct 29	Topic:   Constraint Reasoning in Zero Gravity by Dr. Jeremy Frank, NASA Ames Research Center, (Industrial visitor) Required reading:  Ari Jonsson, Paul Morris, Nicola Muscettola, Kanna Rajan and Ben Smith. " Planning in Interplanetary Space: Theory and Practice." In the Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling, 2000 Recommended reading:   Jeremy Frank and Ari Jonsson. "Constraint-Based Attribute and Interval Planning." Journal of Constraints Special Issue on Constraints and Planning, vol. 8 no 4, 2003.
Mon, Nov 1	Topic:   Minimality and Decomposability Required reading:   Same as above Recommended reading:   Same as above	HWK4 due
Wed, Nov 3	Topic:   Same as above Required reading:   Same as above Recommended reading:   Same as above
Wed, Nov 3	Make-up class from 5:00 p.m. to 6:00 p.m. Topic:   Same as above Required reading:   Same as above Recommended reading:   Same as above	Glossary 5 assigned
Fri, Nov 5	Topic:   Constraint-Based Scheduling by Dr. Markus P.J. Fromherz, Palo Alto Research Center, (Industrial visitor) Required reading: "Constrained-Based Scheduling" Markus Fromherz, Invited Tutorial to the American Control Conference (ACC 01). Recommended reading: Model-Based Computing for Design and Control of Reconfigurable Systems Markus P.J. Fromherz, Daniel G. Bobrow, and J. De Kleer. On-line Planning and Scheduling in a High-speed Manufacturing Domain Wheeler Ruml and Markus P.J. Fromherz.	Class will take place in Avery 351, lunch in Avery 348 Progress reports of projects due (use handin)
Mon, Nov 8	Topic:   Search orders in CSPs Required reading:   Ordering heuristics in CSPs, Tsang 93 Recommended reading:   Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen 92	Glossary 5 due Quiz 6 Homework 5 assigned
Wed, Nov 10	Topic:   same as above (BC, DAC, MAC, DPC) Required reading:   same as above Recommended reading:  same as above	Glossary 6 assigned
Wed, Nov 10	Make-up class or Recitation: Cancelled	Cancelled so that you can work on your projects..
Fri, Nov 12	Topic:   Ordering Heuristics in CSPs Required reading:   Ordering heuristics in CSPs, Tsang 93 Recommended reading:
Mon, Nov 15	Topic:   Same as above Required reading:   Same as above Recommended reading:   Same as above	Glossary 6 due
Wed, Nov 17	Topic:   Dual Viewpoint Heuristics for Binary CSPs Required reading:   Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen (ECAI 92) Recommended reading:
Wed, Nov 17	Make-up class or Recitation from 5:00 p.m. to 6:00 p.m.
Fri, Nov 19	Topic:   Advanced BT Search Required reading:  None, be careful in class! Recommended reading:
Mon, Nov 22	Topic:   Required reading:   Recommended reading:	Homework 5 due
Wed, Nov 24	Student holidady
Wed, Nov 24	Student holiday
Fri, Nov 26	Thanksgiving vacation
Mon, Nov 29	Topic:   Local search Required reading:   see slides Recommended reading:   see slides
Wed, Dec 1	Topic:   Local search Required reading:   see slides Recommended reading:   see slides	No paper presentations, summaries, write-ups, on or after this date
Wed, Dec 1	Make-up class or Recitation from 5:00 p.m. to 6:00 p.m.	Class cancelled, instructor sick.
Fri, Dec 3	Topic:   Finish local search. Presentation by Mythri Required reading:   Frequency Assignment for Cellular Mobile Systems Using Constraint Satisfaction Techniques. Makoto Yokoo and Katsutoshi Hirayama IEEE Annual Vehicular Technology Conference (VTC2000-Spring), pp. 888--894, 2000. Mythri's slides	Final reports of projects due (printed form) Final glossaries due (printed form)
Mon, Dec 6	Topic: PROJECT DEFENSE Attendance is mandatory	Evening meetings if necessary, attendance optional
Wed, Dec 8	Topic: PROJECT DEFENSE Attendance is mandatory
Wed, Dec 8	Topic: PROJECT DEFENSE from 5:00 p.m. to 6:00 p.m. Attendance is mandatory
Fri, Dec 10	Topic: PROJECT DEFENSE Attendance mandatory	Evening meetings if necessary, attendance optional Project code and slides due, use handin
Fri, Dec 17	NO FINAL EXAM