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

Your catch: interesting material you find on the web and that you would like to share. Every student is welcome to propose a link of interest to the class. The student's name will be included. Here is one item proposed by Chris Hammack of the class of Fall 2001, a `real' cool Java Applet: Consistency Based CSP Solver.  Vintage Fall '2002:

Link harvest on Constraint Proesssing:

Link harvest on matters loosely related to the course: Project reports and slides: Handouts:
  1. Syllabus and grading strategy
  2. Algorithms for Constraint Satisfaction Problems: A Survey by Vipin Kumar. AI Magazine Spring 1992.
  3. Constraint Satisfaction Problems, An Overview.  Pedro Meseguer
  4. Constraint Programming: in Pursuit of the Holy Grail. Bartak
  5. Instructor's notes 1
  6. List of projects
  7. The Theory of NP-Completeness. Computers and Intractability, Garey & Johnson (1979), Chapter 2, pages 17--28.
  8. Glossary 1
  9. Instructor's notes 2
  10. Notes of Rina Dechter.
  11. Query Algebra Database System Implementation, pages 240--247, Garcia-Molina, Ullman, Widom. Prentice Hall.
  12. Instructor's notes 3
  13. Glossary 2
  14. Glossary 3
  15. Instructor's notes 4
  16. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems--Mackworth/Freuder
  17. Constraint propagation with interval labels, E. Davis
  18. Glossary 4
  19. Glossary 5
  20. Instructor's notes 5
  21. Instructor's notes 6
  22. Hybrid algorithms for the constraint satisfaction problem--Prosser
  23. Glossary 6
  24. Instructor's notes 7 (width of a graph)
  25. A Theoretical Evaluation of Selected Backtracking Algorithms. Kondrak and van Beek.
  26. Instructor's notes 8
  27.  Search orders in CSPs, Chapter 6, Foundations of Constraint Satisfaction, Tsang
  28. Instructors's notes 9
  29. Slides of the lecture by Dr. Mark Boddy
  30. Slides of Shukla's presentation
  31. Slides of Ashok's presentation
  32. Glossary 7
  33. Slides of Modali's presentation
  34. Binary vs. non-binary representations of constraint-- Bacchus and Van Beek, 98, F. Bacchus and P. van Beek.
  35. Instructor's notes 10
  36. Team evaluation form to be filled by team members working on a team project.
(UNL access only) Most papers are available from the Love Library Electronic reserves. In particular, you can find three chapters of the book by Edward Tsang: Chapter 1, Chapter 6,Chapter 5 Part 1 and  Part 2.

Homework:

You can use the Web Handin System to submit your files, when handin is required.
 
Homework
Date assigned
Due Date
Homework 1 Thursday Sep 5, 2002  Thursday Sep 19, 2002
Submit by pen+paper (or print out) right before class.
Homework2
Use Web Handin System		 Tuesday Sep 24, 2002  Tuesday, Oct 8, 2002. 
Extended to Oct 15, 2002
Homework 3
Use Web Handin System		 Tuesday Oct 15, 2002  Tuesday, Nov 5, 2002. 
Extended to Nov 12, 2002

Schedule:
 
Dat e
Material
Announcements
Tue, Aug 26 Topic:  Overview.
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
    		•   
    Thu, Aug 28  Topic:  Overview
    Required reading:  Same as previous
    Recommended reading:  Same as previous    		 Pretest (20 minutes max). Closed book.
    List of projects has been distributed
    Tue, Sep 3  Topic:  Overview
    Required reading: 
  • Algorithms for Constraint Satisfaction Problems: A Survey by Vipin Kumar. AI Magazine Spring 1992.
  • The Theory of NP-Completeness. Computers and Intractability, Garey & Johnson (1979), Chapter 2, pages 17--28. 

    • Recommended reading:    		 Surprise quiz: Quiz 1
    Thu. Sep 5 Topic: Overview
    Required reading: same as previous
    Recommended reading: same as previous    		 Project topic must be chosen.
    Glossary 1 assigned.
    Homework 1 assigned
    Tue, Sep 10 SAME AS PREVIOUS 
  • WARNING: Last deadline for choosing a project, please submit it via the Web Handin System 
  • Surprise quiz: Quiz 2
  • Office hours of GTA A. Breiner on Wednesdays moved from 10:00 till 11:00 a.m. to 12:00 till 1:00 pm. 
    		•
    Thu, Sep 12 Topic: Same as previous, links between relational DB and CSP
    Required reading: 
  • Notes of Rina Dechter
  • Query Algebra Database System Implementation, pages 240--247,   Garcia-Molina, Ullman, Widom. Prentice Hall. 
    		•  Glossary 1, due
    Glossary 2 assigned
    Tue, Sep 17 opic: Same as previous, links between relational DB and CSP
    Required reading: 
  • Notes of Rina Dechter

    • Query Algebra Database System Implementation, pages 240--247,   Garcia-Molina, Ullman, Widom. Prentice Hall.    		 Glossary 2 due
    Alert: Quiz 3
    Glossary 3 assigned
    Thu, Sep 19 Topic: 
  • Finish: Links between relational DB and CSP
  • Start: Consistency checking 

    • Required reading: 
  • Notes of Rina Dechter
  • Query Algebra Database System Implementation, pages 240--247,   Garcia-Molina, Ullman, Widom. Prentice Hall.
  • The complexity of some polynomial network consistency algorithms for constraint satisfaction problems--Mackworth/Freuder 

    • Recommended reading: 
  • Consistency in networks of relations--Mackworth
  • Constraint propagation with interval labels, E. Davis 
    		•  Homework 1 due.

    Important announcement of additional help sessions in Lisp, by Eric Moss
     
    Tue, Sep 24 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
  • Constraint propagation with interval labels, E. Davis 
  • Path Consistency on Triangulated Constraint Graphs, Bliek, Sam-Haroud, IJCAI 99

    •      		 Alert:  quiz 4
    Glossary 3 is due.
    Glossary 4 assigned
    Homework2 assigned
    Thu, Sep 26 SAME AS PREVIOUS  Bonus by glossary increased to 10%, by popular demand. 
    Tue, Oct 1 SAME AS PREVIOUS  Glossary 4 due. 
    Glossary 5 assigned
    pointers have been added on the main page of the course
  • Constraint Networks, course by Rina Dechter at UCI
  • Constraint Programming Approach to AI Applications, by Michela Milano 
  • The ECLiPSe Constraint Logic Programming System
    		•
    Thu, Oct 3 SAME AS PREVIOUS (AC-1, .... AC-4) Alert:  quiz 5, rescheduled.
    Tue, Oct 8 SAME AS PREVIOUS Homework2 due
    Glossary 5 due
    Thu, Oct 10 Same as previous, focus on Path Consistency Alert: quiz 6
    Tue, Oct 15 Topic: Path Consistency, Minimality, decomposability
    Required reading: same as previous
    Recommended reading:     		 HWK2 due (after extension to Oct 15, 2002)
    Progress report on projects are due.
     Homework 3 assigned
    Thu, Oct 17 Topic: Backtracking algorithms
    Required reading: 
  • Instructor's notes 6
  • Hybrid algorithms for the constraint satisfaction problem--Prosser 

    • Recommended reading:    		 Progress reports due (extension to Oct 17, 2002 granted)
    Tue, Oct 22
    Fall Semester Break
    		  
    Thu, Oct 24 SAME AS PREVIOUS   Cate Anderson anderson@cse.unl.edu is collecting names and checks to arrange for copies of the pre-print of Dechter's new book.  Please make check payable to Kinko's of the amount of US$59.14. 
    Tue, Oct 29 Topic: SAME AS PREVIOUS
    Required reading:  SAME AS PREVIOUS
    Recommended reading:
  • Chapter 5 (Part 1 and Part 2) of Tsang's Book
  • Chapters 5 and 6 of Dechter's new book. (Contact anderson@cse.unl.edu of copies of the pre-print of the book. Cost: $59.14 payable to Kinko's.)
  • Handout 4 (CS329A ) or Handout 5 (CS227) of Pandu Nayak
  • Section 2.4 of Fahiem Bacchus notes
    		•  Glossary 6 assigned
    Alert: Quiz 7
    Thu, Oct 31 Class cancelled.  
    Tue, Nov 5 Same as Tue Oct 29. Homework3 due
    Extension for HWK 3 granted until Nov 12, 2002.
    Thu, Nov 7 Same as previous Glossary 6 due
    Alert: Quiz 8 (announced on Tue in class).  Do the required reading.
    Tue, Nov 12  Topic: Theoretical evaluation of backtracking algorithms. 
    Required reading: A Theoretical Evaluation of Selected 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 (AIJ 2001).    		 Homework3 due
    Thu, Nov 14 Topic: Finish previous discussion. Search order in CSPs.
    Required reading: 
    Ordering heuristics in CSPs, Tsang, Chapter 6.
    Recommended reading:     		  
    Tue, Nov 19  Industrial visitor: Dr. Mark Boddy, Honeywell Laboratories
    Topic: What happens when constraints meet the real world
    Required reading: Temporal Reasonng for Planning and Scheduling in Complex Domains: Lessons Learned. Boddy. Advanced Planning Technology, AAAI Press, 1996.
    Recommended reading: 
  • Hybrid Reasoning for Complex Systems. Boddy & Krebsbach. AAAI Fall Symposium on on Model-directed Autonomous Systems, 1997.
  • A New Method for the Global Solution of Large Systems of Continuous Constraints.  Boddy & Johnson. First International Workshop on Global Constrained Optimization and Constraint Satisfaction (Cocos'02), 2002.
    		•   Please do the required reading.
    Every good question you ask the visitor will be awarded with a bonus point.
    Thu, Nov 21 Topic:  MAC vs FC, presentation by Sudhindra Shukla
    Required reading: AC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems. Bessiere and Regin, CP 96
    Recommended reading:     		  
    Tue, Nov 26 Topic: CSP in Telecom applications, presentation by Ashok Janardhanan
    Required reading: Bandwidth allocation planning in communication networks, Frei and Faltings, Globecom 99
    Recommended reading:     		 Quiz 9 alert
    Glossary 7 assigned
    Thu, Nov 28
    Thanksgiving vacation
    		  
    Tue, Dec 3 Topic: Recent advances in Arc-Consistency, presentation by Srichnan Modali
    Required reading: Refining the Basic Constraint Propagation Algorithm , Besssiere and Regin, IJCAI 2001
    Recommended reading:     		 Quiz 10 alert
    Glossary 7 due
    Thu, Dec 5  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. 
    		•
    Sign up for project presentations
    Tue, Dec 10 Dead week. 
    Project presentations.
    • Team evaluation form to be filled by team members working on a team project.
    • All final reports due.
    • All global glossaries due.
    • Last deadline for submitting a critical summary, chapter, etc.
    Thu, Dec 12 Dead week. 
    Project presentations.
    •  From 9:30 to 10:45 and from 6:00 pm to 8:00 pm
    Tue, Dec 17 Final exam period, scheduled between 10:00 and 12:00, devoted to
    Project presentations.    		  

    Berthe Y. Choueiry

    Last modified: