Detailed Course Schedule

Week 1
Mon, Aug 25 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 
  • Algorithms for Constraint Satisfaction Problems: A Survey (PDF) by Vipin Kumar. AI Magazine Spring 1992.
  • Constraint Satisfaction Problems, An Overview (PDF), Pedro Meseguer 
  • Systematic Search Algorithms, Bartak's online notes
  • Heuristics and Stochastic Algorithms, Bartak's online notes
    • Mon, Aug 25 Recitation: CSP 101
    Wed, Aug 27 Announcements: None
    Topic: Same as above
    Fri, Aug 29
    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, Sep 3
  • Short tutorial on Piazza
  • CSP 101
  • Glossary 1 assigned
    		•
    Week 2
    Mon, Sep 1
    Labor day
    Wed, Sep 3 Announcements:
  • Take home pretest due
  • Homework 1 assigned

    • Topic, required reading, recommended reading: Same as above.
    Fri, Sep 5 Announcements:
  • Glossary 1 due (delayed until Sep 15)
    • Topic: Same as above
    Wed
    Week 3
    Mon, Sep 8
    Instructor out of town
    Graduate student Fikayo Adetundji will be in class during regular lecture and recitation hours and in the SRC during the GTA help session to answer any questions you may have with the homework. It is extremely important that you complete this first homework on time.
    Mon, Sep 8
    Wed, Sep 10
    Fri, Sep 12
    Week 4
    Mon, Sep 15 Announcements:
  • Glossary 1 due
  • Glossary 2 assigned
    • Topic & reading: Arc Consistency
    Required reading:
  • Dechter: Sections 3.1 and 3.2
  • 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)
  • Constraint propagation with interval labels, Davis, AIJ 1987.
    		•
    Mon, Sep 15 Recitation:
    Wed, Sep 17 Topic: Arc Consistency (same as above)
  • Homework 1 due by webhandin by 3:30pm
  • Homework 2 assigned
    		•
    Fri, Sep 19 Announcements:
    Topic: Backtrack Search.
    Required reading: Hybrid algorithms for the constraint satisfaction problem (PDF) Prosser.
    Recommended reading:
  • Chapters 5 and 6, Dechter
  • Chapter 5, Tsang
    		•
    Week 5
    Mon, Sep 22 Announcements:
  • Glossary 2 due
  • Glossary 3 assigned
    Topic: same as above
    • Mon, Sep 22 Recitation:
    Wed, Sep 24 Announcements:
  • Homework 2 Sharing of AC1 results due by 3:30pm

    • Topic: same as above
    Fri, Sep 26 Announcements: Quiz 1
    Topic: Quiz and NP-completeness
    Week 6
    Mon, Sep 29 Announcements:
  • Glossary 3 due
  • Glossary 4 assigned

    • Topic and reading: Backtrack Search (same as above).
    Mon, Sep 29 Recitation:
    Wed, Oct 1 Announcements:
  • Homework 2 due by webhandin by 3:30pm
  • Homework 3 assigned

    • Topic & reading:
    Fri, Oct 3 Announcements:
    Topic:
    Week 7
    Mon, Oct 6 Announcements:
  • Glossary 4 due
  • No new glossary this week, please work on your homework
    • Topic: Theoretical Evaluation of BT Algorithms
    Required reading: A Theorectical Evaluation of Selected Backtracking Algorithms, by Kondrak and van Beek (IJCAI 1995)
    Recommended reading: Dechter, Chapters 5 and 6
    Mon, Oct 6 Recitation:
    Topic: Evaluating & Comparing (Deterministic) BT Search Algorithms
    Wed, Oct 8 Announcements:
  • Quiz 2
  • Homework 3 Progress report due.
    		•
    Fri, Oct 10 Announcements: Quiz 2 re-scheduled for today
    Topic: Search Orders in CSPs (PPT)
    Required reading: Chapter 6, Tsang 93
    Recommended reading:
  • Dechter: Sections: 5.1.1
  • Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen ECAI 92
    		•
    Week 8
    Mon, Oct 13
    Wed, Oct 15
  • Homework 3 due by webhandin by 3:30pm
  • Homework 4 assigned
    		•
    Fri, Oct 17 Announcements:
  • List of project distributed
  • Glossary 5 assigned
    		•
    Week 9
    Mon, Oct 20
    Fall Semester Break
    Mon, Oct 20
    Wed, Oct 22 Announcements:
  • Homework 4 Progress report due.
    		•
    Fri, Oct 24 Announcements:
  • Glossary 5 due
    • 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.
    		•
    Week 10
    Mon, Oct 27 Announcements:
  • Glossary 6 assigned
    		•
    Mon, Oct 27 Recitation: Quiz 3
    Wed, Oct 29 Announcements:
  • Deadline: for project selection. Use webhandin.
  • Homework 4 due by webhandin by 3:30pm
  • Homework 5 assigned
    • Topic: CSPs and DBs
    Required reading: Section 1.3 of Dechter.
    Fri, Oct 31 Announcements:
    Topic: Path Consistency
    Required reading: Dechter: Sections 3.1, 3.2, 3.3, 3.4, 3.5.1, 3.5.3.
    Recommended reading: Chapter 3 entirely.
    Week 11
    Mon, Nov 3 Announcements: Topic, required reading, recommended reading:
    Mon, Nov 3 Recitation: Quiz 4
    Wed, Nov 5 Announcements:
  • Homework 5 Progress report due.
    • Topic: Basics of Constraint-based Scheduling, Nicolas Bonifas
    We will introduce a framework in which to model a generic class of scheduling problems using constraint programming, and explain why scheduling is one of the most successful application of constraint programming. We will also give a brief introduction to the modeling paradigm used in the IBM Ilog CP Optimizer solver.

    Required reading: Philippe Laborie and Jerome Rogerie. Reasoning with Conditional Time-Intervals. FLAIRS conference, 555-560. 2008.

    Recommended reading:
    Fri, Nov 7 Announcements:
    Topic: Propagating the Cumulative Constraint, Nicolas Bonifas
    The cumulative constraint is at the heart of constraint-based scheduling and one of the most famous global constraint. We will give an overview of the different propagation techniques for the cumulative constraint, exposing the trade-offs between propagation speed and propagation strength.

    Required reading: Abder Aggoun and Nicolas Beldiceanu. Extending chip in order to solve complex scheduling and placement problems. Math. Comput. Model., 17(7):57-73, April 1993.

    Recommended reading:
    Week 12
    Mon, Nov 10 Announcement:
  • Class will be held in AvH 347
  • Glossary 6 due

    • Topic: A Taste of SMT Cesare Tinelli
    Recommended reading: Foundations of Lazy SMT and DPLL(T) Tinelli
    Mon, Nov 10 Recitation:
    Announcement: Recitation will be held in AvH 347
    Topic: An Efficient Solver for string and regular expression constraints Cesare Tinelli
    Recommended reading: Foundations of Lazy SMT and DPLL(T) Tinelli
    Wed, Nov 12 Announcements:
  • Homework 5 due by webhandin by 3:30pm.
  • Homework 6 assigned.
    		•
    Fri, Nov 14 Announcements:
    Week 13
    Mon, Nov 17 Announcements:
    Topic, required reading, recommended reading:
    Mon, Nov 17 Recitation: Quiz 5
    Wed, Nov 19 Announcements:
  • Deadline: Progress reports of projects are due. (Use handin)
  • Homework 6 Progress report due.
    		•
    Fri, Nov 21 Announcements:
  • Deadline: First deadline for extra-credit work. At most 1 paper presentation, 2 summaries, 1 chapter write-up after this date.
  • Glossary 7 assigned.

    • Topic: Local Search
    Required reading:
  • Dechter: Section 7.1, and 7.2.
  • Bartak's on-line guide: Heuristic and Stochastic Algorithms
    • Recommended reading:
  • Section 4.3, Chapter 4, in textbook, AI a Modern Approach (Russell & Norvig)
  • Examine the book "Stochastic Local Search" by Hoos and Stuelze
    		•
    Week 14
    Mon, Nov 24 Announcements:
    Topic, required reading, recommended reading:
    Mon, Nov 24 Recitation:
    Wed, Nov 26
  • Homework 6 due Nov 26 by webhandin by 3:30pm
    • Thanksgiving Holiday
    Fri, Nov 28
    Week 15
    Mon, Dec 1 Announcements:
  • Glossary 7 due.
  • Quiz 6

    • Topic, required reading, recommended reading:
  • Quiz may be given
  • Advanced Backtrack Search
    		•
    Mon, Dec 1 Recitation:
  • Quiz may be given
    		•
    Wed, Dec 3 Announcements:
  • Quiz may be given
    		•
    Fri, Dec 5 Announcements:
  • Quiz may be given
  • Deadline: Final glossary due, in print and using handin.
  • Deadline: Project reports are due in print and using handin.
  • Deadline: Second deadline for extra-credit work: No paper presentation, summaries, write-ups, on or after this date.

    • Topic:
    Week 16 (dead week)
    Mon, Dec 8 Announcements:
  • PROJECT DEFENSE. Attendance is mandatory
    . Evening sessions if necessary, attendance is optional.

    • Topic, required reading, recommended reading: TBA.
    Mon, Dec 8 Recitation:
    Wed, Dec 10 Announcements:
  • PROJECT DEFENSE. Attendance is mandatory
    . Evening sessions if necessary, attendance is optional.

    • Topic, required reading, recommended reading: TBA.
    Fri, Dec 12 Announcements:
  • Deadline: Project code and slides due, submit using handin.

    • Topic:
    Week 17
    Wed, Dec 17
    No Final Examination
    7:30—9:30 AM PROJECT DEFENSE
    Attendance is mandatory


    Last modified: Mon Dec 1 14:58:28 CST 2014