Detailed Course Schedule

Dates
Material
Announcements
Week 1
Mon, Jan 14 Topic: Rules of the Game
Required reading:
  • Constraint Programming: in Pursuit of the Holy Grail (PS,PDF). Bartak
    		•  Handouts distributed: syllabus, administrative rules including deadlines, guidelines for reports, Constraint Processing 101.
    Mon, Jan 14 Recitation: Continuation of class  
    Wed, Jan 16
    Pretest
  • In-class: closed book, handwritten crib sheet allowed, must be turned in with test
  • Take-home: collaboration, discussion strictly forbidden. To be returned on Wednesday Jan 21
  • Make sure to check out whether or not you took CSCE310 (or equivalent) and provide your grade.
    		•
    Week 2
    Mon, Jan 21
    Martin Luther King Day
    Wed, Jan 23 Topic: Introduction to CSPs
    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 (PS,PDF). Bartak
    • Recommended reading:  
  • Bartak's on-line guide: Introduction to CSPs
  • Constraint Satisfaction (PDF)  Rina Dechter. MIT Encyclopedia of the Cognitive Sciences 
  • Algorithms for Constraint Satisfaction Problems: A Survey (PDF) by Vipin Kumar. AI Magazine Spring 1992.
  • Constraint Satisfaction Problems, An Overview (PDF), Pedro Meseguer 
    		•  Pretest: Take-home pretest is due.
    Week 3
    Mon, Jan 28

    Topic: CSP 101
    Required reading: same as above
    Recommended reading: same as above

    		 Homework1 (PS, PDF) assigned
    Glossary 1 assigned
    Mon, Jan 28

    Recitation: Same as above

    		 
    Wed, Jan 30

    Topic: Same as above
    Required reading: Same as above
    Recommended reading: Same as above

    		  
    Week 4
    Mon, Feb 4 Topic: Backtrack search and its hybrids
    Required reading: Hybrid algorithms for the constraint satisfaction problem (PDF)--Prosser
    Recommended reading:
  • Chapters 5 and 6, Dechter
  • Chapter 5, Tsang
  • Lecture notes of Fahiem Bacchus: Chapter 2, Section 2.4 (available upon demand)
  • Lecture notes of Pandu Nayad: Handouts 4 & 5
    		•  Glossary 1 due
    Glossary 2 asssigned
    Mon, Feb 4

    Recitation: Correction of Pretest
    Review of NP-Completeness (by Shant)

    		  
    Wed, Feb 6

    Topic: Same as above
    Required reading: Same as above
    Recommended reading: Same as above

    		 Homework 1 due.
    Homework2 (PS, PDF) assigned
    Glossary 3 asssigned
    Week 5
    Mon, Feb 11

    Topics:
    Finish `BT and Its Hybrids'.
    Discussion of Evaluation (deterministic) BT Search Algorithms (PPT)
    Required reading: Dechter 6.6.2
    Recommended reading:

    		Alert: Quiz 1
    Glossary 2, Glossary 3 are both due
    Mon, Feb 11

    Recitation:

    		 
    Wed, Feb 13

    Topics:
    Review of main Lookahead Schemas (PPT)
    Continuation of CSP 101: Overview: advanced solving techniques and research directions (PPT)
    Required reading: Section 5.3 in Dechter.
    Recommended reading:

    		 
    Week 6
    Mon, Feb 18

    Topic: A Theoretical Approach to Backtracking
    Required reading: A Theorectical Evaluation of Selected Backtracking Algorithms (gziped PostScript, Electronic Reserve)
    Recommended reading: The longer and improved paper, which appeared in the AIJ

    		Homework2 (PS, PDF) due
    Homework3 (PS, PDF) assigned
    Mon, Feb 18

    Recitation:
    Shant and Rahul: Quick review of NP-Completeness (PS, PDF).
    Ask your questions about HWK1, HWK2, HWK3...

    		 
    Wed, Feb 20 Topic: Constraints and 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.
    		•  Alert: Quiz 2 in class.
    Glossary 4 assigned
    Week 7
    Mon, Feb 25 Topic: Consistency Algorithms and Consistency Properties
    Required reading:
  • The complexity of some polynomial network consistency algorithms for constraint satisfaction problems--Mackworth/Freuder
  • Sections 3.1, 3.2, 3.3 of Dechter's book.
    • 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 due
    Quiz 3
    Mon, Feb 25

    Recitation:

    		 
    Wed, Feb 27

    Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.

    		 Glossary 5 assigned
    Homework3 (PS, PDF) due: delayed until Friday, Feb 29.
    Fri, Feb 29
    Deadline for project selection. (Use handin.)
    Homework3 (PS, PDF) due. Put/Check results on the wiki.
    Week 8
    Mon, Mar 3

    Topic: Same as above
    Required reading: Same as above
    Recommended reading: Same as above

    		 Homework4 (PS, PDF) assigned. Put/Check results on the wiki.  
    Mon, Mar 3

    Recitation: Finish class discussion, discuss homework

    		  
    Wed, Mar 5

    Topic: Finish Consistency Properties/Methods in CSPs
    Required reading: Dechter Section 3.1--3.3 and 8.1
    Recommended reading: Dechter Chapter 3 and 8, entirely

    		 Glossary 5 due.
    Week 9
    Mon, Mar 10

    Topic: Finish Consistency Properties
    Required reading: Dechter Section 3.1--3.3 and 8.1
    Recommended reading: Dechter Chapter 3 and 8, entirely

    		 Alert: Slides have been updated
    Updated the slides on Consistency: Main Properties and Algorithms for Achieving them (PPT)
    Mon, Mar 10

    Recitation:

    		Alert: Quiz 4
    Wed, Mar 12

    Topic: Ordering heuristics
    Required reading: Ordering heuristics in CSPs, Tsang 93
    Recommended reading: Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen 92

    		 Glossary 6 assigned.
    Week 10
    Mon, Mar 17
    Spring vacation
    Wed, Mar 19
    Week 11
    Mon, Mar 24

    Topic: Same as above
    Required reading: Same as above
    Recommended reading: Brelaz paper on variable ordering heuristic for coloring
    Same as above

    		 Glossary 6 due.
    Homework4 (PS, PDF) due (extended).
    Mon, Mar 24

    Recitation: Fixing CBJ to find all solutions
    (See pages 25-26 of Kondrak's MS thesis (PDF).)

    		 
    Wed, Mar 26

    Topics: Least commitment;
    Local Search (+empirical analysis);
    If time permits: New developments in Backtrack Search
    Required reading: Dechter: Section 7.1, and 7.2. (for local search)
    Recommended reading: ECLiPSe: Chapter 12 on Search (for new developments in backtrack search)

    		Homework4 (PS, PDF) due (extension).
    Fri, Mar 28
    Progress reports of projects are due. (Use handin.)
    Week 12
    Mon, Mar 31

    Topic: Same as above
    Required reading: Same as above
    Recommended reading: Same as above

    		 Glossary 7 assigned
    Alert: I have made a number of random generator available online (see Online Resources in the left vertical menu)
    Mon, Mar 31

    Recitation:  

    		Statistical help with your experiments: The Statistics Department at UNL maintains a Helpdesk in Avery Hall (and also Hardin Hall on East Campus). I strongly encourage you to visit them for support in the analysis of your experiments.
    Wed, Apr 2 Topic: Same as above
    Required reading: Same as above
    Recommended reading: Same as above     		 
    Week 13
    Mon, Apr 7 Topic: An Efficient Filtering for AllDiff Constraints
    Required reading: A Filtering Algorithm for Constraints of Differences in CSPs-- Regin, AAAI 1994.
    Recommended reading: Dechter: Sections 3.5.2, 3.5.3 and 15.5.3     		 
    Mon, Apr 7 Recitation: from 5:00 to 5:50 pm

      

    Wed, Apr 9 Topic: Nonbinary CSPs: mappings, FC
    Required reading:
  • Binary vs. non-binary representations of constraint-- Bacchus and van Beek, 98.
  • On Forward Checking for Non-Binary Constraint Satisfaction-- Besisère, Meseguer, Freuder, and Larossa, AIJ 2002.
    • 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.
    		•  Homework5 (PS, PDF) assigned. HWK 5 was cancelled by unanimous agreement.
    Fri, Apr 11
    First deadline for extra-credit work: At most 1 paper presentation, 2 summaries, 1 chapter write-up after this date.
    Week 14
    Mon, Apr 14 Topic: Introduction to Tree-Based Methods (Decomposition)
    Recommended reading:
  • 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
  • Tree Clustering for Constraint Networks Dechter and Pearl, AIJ 1989
  • More papers on Tree-Based Techniques are available upon request.
    		•   
    Mon, Apr 14

    Recitation:
    Discussing content of HWK 5

    		 
    Wed, Apr 16

    Topic: Same as above. t-test
    Required reading: Same as above

    		  
    Week 15
    Mon, Apr 21 Topic: A Case Study of Network Design
    A lecture by industrial researcher Dr. Jean-Charles Régin of Ilog
    Slides: Network Design, CP Challenges, and Principles of CP (CSE Colloquium). Check details from the visit page.
    Required reading:
    Robust and Parallel Solving of a Network Design Problem ( PS, PDF).
    Recommended reading:
    Papers on modeling:
  • Minimizing the Number of Breaks in Sports Scheduling Problems Using Constraint Programming (PS, PDF).
  • Constraint Programming in OPL (PS, PDF).
    • Chapter on Global Constraints:
  • Global Constraints and Filtering Algorithms (PS, PDF).
    		•  Please confirm if you are attending dinner at The Oven
    Mon, Apr 21

    Recitation:

     

    		 Time for discussion before dinner.
    Wed, Apr 23 Topic: A Review of Choco, a Constraint Programming System
    by Suzette Person
    Required reading:
    Recommended reading:
  • User Guide
  • Laburthe's paper Implementing a CP Kernel.
    		•  A quiz may be given in class
    Fri, Apr 25
  • Final glossary due, in print and using handin.
  • Project reports are due in print and using handin.
  • Second deadline for extra-credit work: No paper presentation, summaries, write-ups, on or after this date.
    		•
    Week 16
    Mon, Apr 28

    Topic: PROJECT DEFENSE
    Attendance is mandatory

    		  
    Mon, Apr 28 Recitation from 5:00 to 6:00 pm

    Topic: PROJECT DEFENSE
    Attendance is mandatory

    		  
    Wed, Apr 30

    Topic: PROJECT DEFENSE
    Attendance is mandatory

    		 Evening sessions if necessary, attendance is optional
    Fri, May 2
    Project code and slides due, submit using handin.
    Week 17
    Wed, May 7
    No Final Examination


    Last modified: Thu Apr 9 23:25:05 CDT 2009