Detailed Course Schedule

Week 1
Mon, Aug 24 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 24 Recitation: None today
    Wed, Aug 26 Topic, required reading, recommended reading: Same as above
  • Short tutorial on Piazza
  • Refresher on Handin
    		•
    Fri, Aug 28
    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 2
  • CSP 101
  • Glossary 1 assigned
    		•
    Week 2
    Mon, Aug 31 Topic, required reading, recommended reading: Same as above.

    Announcements:
  • Take home pretest due
  • Homework 1 assigned
  • Glossary 1 assigned
    		•
    Mon, Aug 31 Recitation: Homework 1 Tutorial
    Wed, Sep 2 Topic, required reading, recommended reading: Same as above.
    Announcement: None.
    Fri, Sep 4 Topic, required reading, recommended reading: Same as above.
    Announcements: None.
    Week 3
    Mon, Sep 7
    Labor day
    Wed, Sep 9 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement:
  • Glossary 1 due.
    		•
    Fri, Sep 11 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
  • Glossary 2 assigned
    		•
    Week 4
    Mon, Sep 14 Topic: Arc Consistency.

    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None.
    Mon, Sep 14 Recitation: NP Completeness
    Wed, Sep 16 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 21 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:
  • Glossary 3 assigned
    		•
    Mon, Sep 21 Recitation:
    Wed, Sep 23 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: None.
    Fri, Sep 25 Topic: Backtracking Search: BJ, CBJ.

    Required reading: Same as Monday, Sep, 21.
    Recommended reading: Same as Monday, Sep, 21.
    Announcement:
  • Homework 2 due
  • Homework 3 assigned
    		•
    Week 6
    Mon, Sep 28 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 28 Recitation:
    Wed, Sep 30 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None.
    Fri, Oct 2 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 5 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 5 Recitation:
    Wed, Oct 7 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None.
    Fri, Oct 9 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:
  • Homework 3 due
  • Homework 4 assigned
    		•
    Week 8
    Mon, Oct 12 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement:
  • Glossary 5 due
    		•
    Mon, Oct 12 Recitation:
  • Quiz 4
  • Profiling your code with Java VisualVM (Robert Woodward).
    		•
    Wed, Oct 14 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None.
    Fri, Oct 16 Announcements:
  • List of project distributed
  • Homework 4 Progress Report due
    		•
    Week 9
    Mon, Oct 19
    Fall Semester Break
    Wed, Oct 21 Topic: DB vs CSP.

    Required reading: Section 1.3 of Dechter.

    Announcement:
  • Glossary 6 assigned
    		•
    Fri, Oct 23 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None.
  • Homework 4 due
  • Homework 5 assigned
    		•
    Week 10
    Mon, Oct 26 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:
  • Glossary 6 due
  • Glossary 7 assigned
  • Quiz 5
    • Mon, Oct 26 Recitation:
  • Quiz 5
    • Wed, Oct 28 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcements:
  • Deadline: for project selection. Use handin.
    		•
    Fri, Oct 30 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: x.
  • Homework 5 Progress Report due
    • Week 11
    Mon, Nov 2 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, Nov 2 Recitation:
  • Quiz 6
  • Quiz 7
    • Wed, Nov 4 Topic: Partial Path Consistency.

    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None.
    Fri, Nov 6 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 9 Topic: Advanced BT Search.

    Required reading: None.

    Recommended reading:
  • ECLiPSe: Chapter 12 on Search (Credit-Based Search)
  • Limited Discrepancy Search, Harvey and Ginsberg, copyright IJCAI 1995
  • Boosting Combinatorial Search Through Randomization, Gomes et al, AAAI 1998.
  • Search in a Small World, Walsh, IJCAI 1999.

    • Announcement: None.
    Mon, Nov 9 Recitation:
  • Quiz 8
    • Wed, Nov 11 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None.
    Fri, Nov 13 Topic: Least Commitment.

    Required reading: None.
    Recommended reading: None.

    Announcement:
  • Homework 6 Progress Report due
    		•
    Week 13
    Mon, Nov 16 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 9 assigned
    		•
    Mon, Nov 16 Recitation:
  • Quiz 9
  • 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 18 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement:
  • Deadline: Progress reports of projects are due. (Use handin)
    		•
    Fri, Nov 20 Topic: x.
    Required reading: x.
    Recommended reading: x.
    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 23 Topic: x.
    Required reading: x.
    Recommended reading: x.
    Announcement:
  • Glossary 9 due
    • Mon, Nov 23 Recitation:
  • Quiz 10
    • Wed, Nov 25 Topic: Graphical Representration and Graphical Models

    Required reading: Hypergraph, primal graph, dual graph, incidence graph.
    Recommended reading: x.
    Announcement: None.
    Fri, Nov 27
    Thanksgiving Holiday
    Week 15
    Mon, Nov 30 Topic: Structure-Based Techniques

    Required reading:
  • Dechter Sections: 2.1.3, 5.1.2, 10.1.1, 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 30 Recitation:
  • Quiz may be given
  • Alert: Each student must make two statements, questions, remarks, etc. about his her project.
    		•
    Wed, Dec 2 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Announcement: None.
    Fri, Dec 4 Topic: x.
    Required reading: x.
    Recommended reading: x.
    Announcements:
  • Quiz may be given
  • Deadline: Final glossary 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 7 Announcements:
  • PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
    		•
    Mon, Dec 7 Recitation:
  • PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
    		•
    Wed, Dec 9 Announcements:
  • Deadline: Project reports are due in print and using handin.
  • PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
    		•
    Fri, Dec 11 Announcements:
  • PROJECT DEFENSE. Attendance is mandatory. (Evening sessions if necessary, attendance is optional.)
  • Deadline: Project code and slides due, submit using handin.
    		•
    Week 17
    Mon, Dec 14
    No Final Examination
    8:30—10:30 AM PROJECT DEFENSE
    Attendance is mandatory


    Last modified: Wed Dec 2 19:16:08 CST 2015