Detailed Course Schedule

Week 1
Mon, Aug 20 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 20 Recitation: CSP 101
    Wed, Aug 22 Announcements: None
    Topic: Same as above
    Fri, Aug 24
    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, August 27
  • CSP 101
  • Glossary 1 assigned
    		•
    Week 2
    Mon, Aug 27 Announcements: Homework 1 assigned
    Topic: Same as above
    Mon, Aug 27 Recitation:
    Wed, Aug 29 Announcements:
    Topic, required reading, recommended reading: Same as above.
    Fri, Aug 31 Announcements:
  • Takehome pretest due
  • Glossary 1 due
    • Topic: Same as above
    Week 3
    Mon, Sep 3
    Labor day
    Wed, Sep 5 Announcements: Homework 1 due by webhandin Due Friday by 3:30pm
    Topic: 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.
    		•
    Fri, Sep 7 Announcements:
  • Homework 1 due by webhandin by 3:30pm
  • Homework 2 assigned
  • Glossary 2 assigned
    • Topic: Arc Consistency (same as above)
    Week 4
    Mon, Sep 10 Topic & reading: Same as above
    Mon, Sep 10 Recitation:
  • Quiz 1
    • Wed, Sep 12 Topic: Arc Consistency (same as above)
    Fri, Sep 14 Announcements:Glossary 2 due
    Topic: Same as above
    Week 5
    Mon, Sep 17 Announcements: Homework 2 due by webhandin by 3:30pm
    Topic: Arc Consistency (same as above)
    Mon, Sep 17 Recitation: Quiz 2
    Wed, Sep 19 Announcements: Glossary 3 assigned
    Topic: Backtrack Search.
    Required reading: Hybrid algorithms for the constraint satisfaction problem (PDF) Prosser.
    Recommended reading:
  • Chapters 5 and 6, Dechter
  • Chapter 5, Tsang
    		•
    Fri, Sep 21 Announcements:Homework 2 due
    Topic: Backtrack Search (same as above)
    Week 6
    Mon, Sep 24 Announcements:Glossary 3 due
    Topic and reading: Backtrack Search (same as above).
    Mon, Sep 24 Recitation: Cancelled
    Wed, Sep 26 Announcements: Homework 3 assigned
    Topic & reading: BT Search, same as above
    Fri, Sep 28 Announcements:
    Topic:
    Week 7
    Mon, Oct 1 Topic: Modeling examples: Minesweeper, Game of Set (Odds & Ends)
    Mon, Oct 1 Recitation:
  • Quiz 3
  • discussion about homework
    		•
    Wed, Oct 3 Announcements:
  • No class, instructor sick.
  • Homework 3 progress report due
  • Homework 4 assigned
    		•
    Fri, Oct 5 Announcements:
    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
    Week 8
    Mon, Oct 8
    Instructor out of town
    Wed, Oct 10
    Fri, Oct 12
    Week 9
    Mon, Oct 15
    Fall Semester Break
    Mon, Oct 15
    Wed, Oct 17 Announcements:
  • Homework 3 due
  • Homework 4 due
    		•
    Fri, Oct 19 Announcements:
    Topic:
    Week 10
    Mon, Oct 22 Announcements:
  • Glossary 4 assigned
    • Topic: CSPs and DBs
    Required reading: Section 1.3 of Dechter.
    Mon, Oct 22 Recitation: Finishing discussion on graphical representations (hypergraph, primal, dual, Odds & Ends)
    Wed, Oct 24 Announcements:
  • Quiz 4
  • List of project distributed

    • 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
    		•
    Fri, Oct 26 Announcements: None.
    Topic, required & recommended reading: Same as above.
    Week 11
    Mon, Oct 29 Announcements:
  • Homework 5 progress report due (on handin, submit it in the Homework 5 handin in a plain text file).
  • Glossary 4 due.
    • Topic, required reading, recommended reading: Same as on Oct 24.
    Mon, Oct 29 Recitation:
    Wed, Oct 31 Announcements:
  • Deadline: for project selection. Use webhandin.
  • Glossary 5 assigned.
    • Topic: Finish Search Orders in CSPs Required reading: Same as above.
    Fri, Nov 2 Announcements:
    Topic: Path Consistency & Global Consistency Properties
    Required reading:
  • Dechter: Sections 3.1, 3.2, 3.3, 3.4, 3.5.1, 3.5.3.
  • The complexity of some polynomial network consistency algorithms for constraint satisfaction problems Mackworth & Freuder, AIJ 1985 (only AC algorithms)
    • Recommended reading:
  • Chapter 3 of Dechter, entirely
  • Path Consistency on Triangulated Constraint Graphs, Bliek, Sam-Haroud, IJCAI 1999.
    		•
    Week 12
    Mon, Nov 5 Announcements:
  • Homework 5 due.

    • Topic, required reading, recommended reading: Same as above
    Mon, Nov 5 Recitation: Quiz 5
    Wed, Nov 7 Announcements:
  • Homework 6 assigned.
  • Glossary 5 due
  • Glossary 6 assigned

    • Topic: Same as above (Path Consistency & Global Consistency Properties)
    Fri, Nov 9 Announcements: 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 13
    Mon, Nov 12 Announcements:
    Topic, required reading, recommended reading: TBA.
    Mon, Nov 12 Recitation:
  • Quiz 6
    • Wed, Nov 14 Announcements:
  • Deadline: Progress reports of projects are due. (Use handin)
  • Glossary 6 due
  • Glossary 7 assigned
    • 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.
    • Fri, Nov 16 Announcements:
  • Deadline: First deadline for extra-credit work. At most 1 paper presentation, 2 summaries, 1 chapter write-up after this date.

    • Topic: Same as above (AllDiff)
    Week 14
    Mon, Nov 19 Announcements:
  • Homework 6 due
  • Glossary 7 due

    • Topic, required reading, recommended reading: Same as above
    Mon, Nov 19 Recitation:
    Wed, Nov 21
    Thanksgiving Holiday
    Fri, Nov 23
    Week 15
    Mon, Nov 26 Announcements:
  • Quiz 7

    • Topic, required reading, recommended reading:
    Mon, Nov 26 Recitation:
  • Quiz may be given
    		•
    Wed, Nov 28 Announcements:
  • Quiz may be given

    • Topic, required reading, recommended reading: TBA.
    Fri, Nov 30 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 3 Announcements:
  • PROJECT DEFENSE. Attendance is mandatory
    . Evening sessions if necessary, attendance is optional.

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

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

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


    Last modified: Wed Nov 14 15:17:25 CST 2012