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 
  • 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
    • Wed, 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 29
  • CSP 101
    		•
    Week 2
    Mon, Aug 29 Announcements:
  • Pretest: Take-home pretest is due
  • Homework 1 assigned
  • Glossary 1 assigned

    • Topic, required reading, recommended reading: Same as above
    Wed, Aug 31 Announcements:Please prepare any questions you may have about the slides, required and/or recommended readings.
    Topic, required reading, recommended reading: Same as above.
  • Glossary 4 due.
    • Week 3
    Mon, Sep 5
    Labor day
    Wed, Sep 7 Announcements:
  • Homework 1 due by webhand
  • Homework 2 assigned
  • Glossary 1 due on paper

    • 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.
    		•
    Week 4
    Mon, Sep 12 Announcements:
  • Glossary 1 due
  • Instructor out of town, will be replaced by Robert to discuss AC1, AC3, experiments, HWK2

    • Topic, required reading, recommended reading: Same as Sep 7.
    Wed, Sep 14 Announcements:
  • Glossary 1 due
  • Instructor out of town, will be replaced by Robert to discuss AC1, AC3, experiments, HWK2

    • Topic, required reading, recommended reading: Same as Sep 7.
    Week 5
    Mon, Sep 19 Announcements:
  • Homework 2 delayed
  • Homework 3 assigned. See email and homework schedule.
  • Instructor out of town, will be replaced by Robert or Shant to discuss experiments and t-test.

    • Topic, required reading, recommended reading: TBA.
    Wed, Sep 21 Announcements: Let's discuss deadlines for HWK2 and HWK3.

    Topic Odds & Ends, CSP 101--Overview
  • Instructor's slides: Odds & Ends (PPT)
  • Instructor's slides: Constraint Processing 101 (PPT)
  • Quick review of NP-Completeness (by Shant and Rahul).

    • Required reading, recommended reading: Same as on Week 1.
    Week 6
    Mon, Sep 26 Announcements:
  • Glossary 2 assigned
  • Homework 2 due
  • Deadline for Homework 3 to be discussed

    • Topic: Backtrack Search.
    Required reading: Hybrid algorithms for the constraint satisfaction problem (PDF) Prosser.
    Recommended reading:
  • Chapters 5 and 6, Dechter
  • Chapter 5, Tsang
    		•
    Wed, Sep 28 Announcements:
  • Homework 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
    		•
    Week 7
    Mon, Oct 3 Announcements:
  • Glossary 2 due
  • Glossary 3 assigned
  • Homework 2 due

    • Topic, required reading, recommended reading: Same as Sep 28.
    Wed, Oct 5 Announcements:
  • List of projects for Fall 2011

    • Topic, required reading, recommended reading: Same as Sep 28.
    Week 8
    Mon, Oct 10 Announcements:
  • Glossary 3 due
  • Homework 3 due
  • Homework 4 assigned

    • 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
    Wed, Oct 12 Announcements:
    Topic, required reading, recommended reading: Same as above.
    Week 9
    Mon, Oct 17
    Fall Semester Break
    Wed, Oct 19 Announcements:
  • Glossary 4 assigned
  • Deadline: for project selection. Use handin.

    • Topic, required reading, recommended reading: Finsih topic of Oct, 10.
    Topic & required reading: CSPs and DBs. Section 1.3 of Dechter.
    Topic: Path Consistency Required reading: Dechter Chapter 3, entirely
    Week 10
    Mon, Oct 24 Announcements:
  • Homework 4 due

    • Topic, required reading, recommended reading: Same as on Oct 19.
    Wed, Oct 26 Announcements:
    Topic, required reading, recommended reading: Same as on Oct 19.
    Week 11
    Mon, Oct 31 Announcements: Homework 5 assigned
    Topic, required reading, recommended reading: Same as on Oct 19.
    Wed, Nov 2 Announcements:
    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 12
    Mon, Nov 7 Announcements: Homework 5 was due, delayed
    Topic, required reading, recommended reading: Same as on Nov 2.
    Wed, Nov 9 Announcements:
  • Glossary 5 assigned
  • Glossary 6 assigned
  • Homework 6 assigned

    • Topic:
  • Finish Search Orders in CSPs (PPT)
  • Local Search (PPT).

    • 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), by Hoos and Stuelze
    		•
    Week 13
    Mon, Nov 14 Announcements:
  • Glossary 5 due
  • 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.

    • Topic, required reading, recommended reading: TBA.
    Wed, Nov 16 Announcements:
  • Homework 6 due
  • Homework 7 assigned
  • Glossary 6 due
  • Glossary 7 assigned
  • Deadline: First deadline for extra-credit work. At most 1 paper presentation, 2 summaries, 1 chapter write-up after this date.

    • Topic, required reading, recommended reading: TBA.
    Week 14
    Mon, Nov 21 Announcements:
  • Homework 6 due
  • Glossary 7 assigned
  • 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.

    • Topic, required reading, recommended reading: TBA.
    Wed, Nov 23
    Thanksgiving Holiday
    Week 15
    Mon, Nov 28 Announcements:
  • Each student must make two statements, questions, remarks, etc. about his her project.
  • A quiz may be given in class

    • Topic, required reading, recommended reading: TBA.
    Wed, Nov 30 Announcements:
  • Homework 7 due
  • 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, required reading, recommended reading: TBA.
    Week 16 (dead week)
    Mon, Dec 5 Announcements:
  • PROJECT DEFENSE. Attendance is mandatory
    . Evening sessions if necessary, attendance is optional.

    • Topic, required reading, recommended reading: TBA.
    Wed, Dec 7 Announcements:
  • PROJECT DEFENSE. Attendance is mandatory
    . Evening sessions if necessary, attendance is optional.
  • Deadline: Project code and slides due, submit using handin.

    • Topic, required reading, recommended reading: TBA.
    Week 17
    Tue, Dec 13
    No Final Examination
    8:30--10:30 PMj PROJECT DEFENSE
    Attendance is mandatory


    Last modified: Wed Nov 30 16:18:15 CST 2011