CSCE 421/821

Foundations of Constraint Processing

Detailed Course Schedule

Week 1
Mon, Aug 22 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 (PPT)
  • Quick review of NP-Completeness (by Shant and Rahul).

    • 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
    • Mon, Aug 22 Recitation:
  • Short tutorial on Piazza
  • Refresher on Handin
  • About using Grader
    		•
    Wed, Aug 24 Topic, required reading, recommended reading: Same as above
    Fri, Aug 26
    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 Monday, Aug 29
  • CSP 101
    		•
    Week 2
    Mon, Aug 29 Topic, required reading, recommended reading: Same as above.

    Announcements:
  • Take home pretest due
  • Homework 1 assigned
  • Glossary 1 assigned
    		•
    Mon, Aug 29 Recitation: Homework 1 Tutorial
    Wed, Aug 31 Topic, required reading, recommended reading: Same as above.
    Announcement: None.
    Fri, Sep 2 Class cancelled because of foreign visitors.
    All are welcome to attend workshop "Computer Intelligence and Smart Sensing" in AvH 347.
    Week 3
    Mon, Sep 5
    Labor day
    Wed, Sep 7 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement:
  • Glossary 1 due.
    		•
    Fri, Sep 9 Topic: Finish overview, start Arc Consistency.

    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, Sep 12 Topic: Arc Consistency.

    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: Glossary 2 assigned.
    Mon, Sep 12 Recitation: NP Completeness
    Wed, Sep 14 Topic: Finish Arc Consistency: AC-4. Start Backtrack Algorithms.

    Required reading:
  • Same as above
  • Hybrid algorithms for the constraint satisfaction problem (PDF) Prosser

    • Recommended reading:
  • Chapters 5 and 6, Dechter
  • Chapter 5, Tsang

    • Announcement: None.
    Fri, Sep 18 Topic: AC3.1/2001. Quiz.

    Required reading: Same as above.

    Recommended reading:
  • Paper on AC3.1/2001: An Optial Coarse-Grained Arc Consistency Algorithm (PDF) Bessiere et al., AIJ 2005

    • Announcement:
  • Quiz 1
  • Homework 2 Initial AC1 due
  • Glossary 2 due
    		•
    Week 5
    Mon, Sep 19 Topic: Backtracking Search.

    Required reading:
  • Hybrid algorithms for the constraint satisfaction problem (PDF) Prosser

    • Recommended reading:
  • Chapters 5 and 6, Dechter
  • Chapter 5, Tsang

    • Announcement: None
    Mon, Sep 19 Recitation:
    Wed, Sep 21 Topic:Evaluation of Deterministic Algorithms for CSPs.

    Required reading:
  • Peter Cheeseman et al.: Where the Really Hard Problems Are (IJCAI 1991).

    • Recommended reading: Same as above.
    Announcement:
  • Glossary 3 assigned
    		•
    Fri, Sep 23 Topic: Backtracking Search: BJ, CBJ.

    Required reading: Same as Monday, Sep 19.
    Recommended reading: Same as Monday, Sep 19.
    Announcement:
  • Homework 2 due
  • Homework 3 assigned
    		•
    Week 6
    Mon, Sep 26 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement:
  • Glossary 3 due
  • Glossary 4 assigned
  • Quiz 2
    • Mon, Sep 26 Recitation:
    Wed, Sep 28 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None.
    Fri, Sep 30 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

    • Announcement:
  • Homework 3 Progress Report due
    		•
    Week 7
    Mon, Oct 3 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement:
  • Glossary 4 due
  • Glossary 5 assigned
  • Quiz 3
    • Mon, Oct 3 Recitation:
    Wed, Oct 5 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None.
    Fri, Oct 7 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:
  • Homework 3 due
  • Homework 4 assigned
    		•
    Week 8
    Mon, Oct 10 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement:
  • Glossary 5 due
  • Glossary 6 assigned
    		•
    Mon, Oct 10 Recitation:
  • Quiz 4
    		•
    Wed, Oct 12 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
    • Fri, Oct 14 Topic:
  • SAT and reducing a CSP into SAT (another example of problem reduction)
  • Open-ended discussion before Fall break
    • Announcements:
  • List of project distributed
  • Homework 4 Progress Report due
    		•
    Week 9
    Mon, Oct 17
    Fall Semester Break
    Wed, Oct 19 Topic: Same as above

    Required reading: Same as above.

    Announcement:
  • Project list distributed in class, in print.
    		•
    Fri, Oct 21 Topic: DB vs CSP.

    Required reading: Section 1.3 of Dechter.
    Announcement:
  • Homework 4 due
  • Homework 5 assigned
    		•
    Week 10
    Mon, Oct 24 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 6 due
  • Glossary 7 assigned
  • Quiz 5
    • Mon, Oct 24 Recitation:
  • Quiz 5
    • Wed, Oct 26 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcements:
  • Deadline: for project selection. Use handin.
    		•
    Fri, Oct 28 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: x.
  • Homework 5 Progress Report due
    • Week 11
    Mon, Oct 31 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

    • Announcement:
  • Glossary 7 due
  • Glossary 8 assigned
    • Mon, Oct 31 Recitation:
  • Quiz 6
    • Wed, Nov 2 Topic: Partial Path Consistency.

    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None.
    Fri, Nov 4 Topic: Global Consistency Properties.

    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None.
  • Homework 5 due
  • Homework 6 assigned
    		•
    Week 12
    Mon, Nov 7 Topic: Local Search

    Required reading:
  • Dechter, Chapter 7
  • Heuristics and Stochastic Algorithms (Bartak's online notes)

    • Recommended reading:
  • 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:
  • Glossary 8 due
  • Glossary 9 assigned
    		•
    Mon, Nov 7 Recitation: Will continue lecture to catch up on material
    Wed, Nov 9 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement:
  • Quiz 7
    • Fri, Nov 11 Topic: Least Commitment.

    Required reading: None.
    Recommended reading: None.

    Announcement:
  • Homework 6 Progress Report due
    		•
    Week 13
    Mon, Nov 14 Topic: More on Backtrack Search
    Required reading: Refer to slides.
    Announcement:
  • Glossary 9 due
    		•
    Mon, Nov 14 Recitation:
  • Quiz 8
  • Alert: Each student must make two statements, questions, remarks, etc. about his/her project.
    Rationale: You can state a difficulty you are having, a barrier you overcame, a new idea you learned about, whatever information you wish to share about your project.
    		•
    Wed, Nov 16 Topic: Graphical Representations of CSPs.
    Required reading: Refer to slides and Index of textbook.
    Announcement:
  • Deadline: Progress reports of projects are due. (Use handin)
    		•
    Fri, Nov 18 Topic: More on Constraint Consistency.
    Required reading: Refer to slides and Index of textbook. >
    Announcement:
  • Deadline: First deadline for extra-credit work. At most 1 paper presentation, 2 summaries, 1 chapter write-up after this date.
  • Homework 6 due
    		•
    Week 14
    Mon, Nov 21 Topic: Graphical Representration and Graphical Models

    Required reading: Hypergraph, primal graph, dual graph, incidence graph.
    Recommended reading: x.
    Announcement: None.
    Mon, Nov 21 Recitation:
  • Quiz 9
    • Wed, Nov 23
    Thanksgiving Holiday
    Fri, Nov 25
    Week 15
    Mon, Nov 28 Topic: 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

    • Announcement: x.
    Mon, Nov 28 Recitation:
  • Quiz 10may be given
  • Alert: Each student must make two statements, questions, remarks, etc. about his her project.
    		•
    Wed, Nov 30 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None.
    Fri, Dec 2 Topic: x.
    Required reading: x.
    Recommended reading: x.
    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, summaries, write-ups, on or after this date.
    		•
    Week 16 (dead week)
    Mon, Dec 5 Announcements:
  • PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
    		•
    Mon, Dec 5 Recitation:
  • PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
    		•
    Wed, Dec 7 Announcements:
  • PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
    		•
    Fri, Dec 9 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
    Mon, Dec 12
    No Final Examination
    8:30—10:30 AM PROJECT DEFENSE
    Attendance is mandatory