Detailed Course Schedule

Dates
Material
Announcements
Week 1
Mon, Jan 12 Topic: Rules of the Game
Required reading: Syllabus. 		Handouts distributed: (1) syllabus and administrative rules including deadlines, (2) guidelines for reports, (3) Constraint Processing 101.
Wed, Jan 14 Topic: Introduction to CSPs
  • Dechter: Section 1.1, 1.3.3, 1.3.4, 2.1 and 2.2.
  • Constraint Programming: in Pursuit of the Holy Grail (PS,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 
    		•   
    Wed, Jan 14 Recitation: Continuation of class  
    Fri, Jan 16
    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 Jan 21
    		•
    Week 2
    Mon, Jan 19
    Martin Luther King Day
    Wed, Jan 21 Topic: Introduction to CSPs
    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 (PS,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 
    		•  Pretest: Take-home pretest is due.
    Glossary 1 assigned
    Wed, Jan 21 Recitation: CSP 101
    		  
    Fri, Jan 23 Topic: Same as before
    Required reading: Same as before
    Recommended reading: Same as before
    Week 3
    Mon, Jan 26 Topic: CSP 101
    Required reading: Same as before
    Recommended reading: Same as before
  • Glossary 1 due
  • Homework 1 assigned
  • Glossary 2 assigned
    		•
    Wed, Jan 28 Topic: CSP 101
    Required reading: Same as above
    Recommended reading:
  • Systematic Search Algorithms (Bartak's online notes)
  • Heuristics and Stochastic Algorithms (Bartak's online notes)
    		•  
    Wed, Jan 28 Recitation: A discussion of NP-Completeness ( PDF), lead by Shant.  
    Fri, Jan 30 Topic: Backtrack Search
    Required reading:
  • Hybrid algorithms for the constraint satisfaction problem (PDF)--Prosser
    • Recommended reading:
  • Chapters 5 and 6, Dechter
  • Chapter 5, Tsang
  • Lecture notes of Fahiem Bacchus: Chapter 2, Section 2.4 (available upon demand)
    		•
    Week 4
    Mon, Feb 2 Topic: Same as above
    Required reading: Same as above
    Recommended reading: Same as above
  • Glossary 2 due
  • Glossary 3 assigned
  • Quiz 1
    • Wed, Feb 4 Topic: Same as above
    Required reading: Same as above
    Recommended reading: Same as above
  • Homework 1 due
  • Homework 2 assigned
    		•
    Wed, Feb 4 Recitation: Homework 2 discussion.
    		 If you have any questions, please quickly ask.
    Fri, Feb 6 Topic: Same as above. Lookahead techniques, if time permits.
    Required reading: Same as above. Dechter Sections 5.3.1 and 5.3.2
    Recommended reading: Same as above
    Week 5
    Mon, Feb 9 Topics:
  • Lookahead Schemas (PPT)
  • Continuation of CSP 101: Overview: advanced solving techniques and research directions
    • Required reading:
  • Freuder and Hubbe: A Disjunctive Decomposition Control Schema for Constraint Satisfaction (CP 1993)
  • Peter Cheeseman et al.: Where the Really Hard Problems Are (IJCAI 1991).
  • Sections 5.3.1 and 5.3.2 in Dechter.
    • Recommended reading: The rest of Section 5.3 in Dechter.
  • Glossary 3 due
  • Glossary 4 assigned
    		•
    Wed, Feb 11 Topics:
  • Continuation of CSP 101: Overview: advanced solving techniques and research directions
    • Required reading:
  • Freuder and Hubbe: A Disjunctive Decomposition Control Schema for Constraint Satisfaction (CP 1993)
  • Peter Cheeseman et al.: Where the Really Hard Problems Are (IJCAI 1991).
    • Recommended reading:     		 
    Wed, Feb 11 Recitation:
  • Quiz
  • Homework discussion
  • Continue CSP 101
  • Quiz 2
  • If you have any questions about homework, please quickly ask.
    		•
    Fri, Feb 13 Topic:
  • DB & CSP
  • Theoretical Evaluation of BT Algortithms
    • Required reading:
  • Section 1.3 of Dechter
  • A Theorectical Evaluation of Selected Backtracking Algorithms, by Kondrak and van Beek (IJCAI 1995)
    • Recommended reading: Dechter, Chapters 5 and 6
  • Homework 2 due
    • Week 6
    Mon, Feb 16 Topic: Same as above.
    Required reading: Same as above
    Recommended reading: Same as above.
  • Homework 2 due
  • Homework 3 assigned
  • Glossary 4 due
  • Glossary 5 assigned
    		•
    Wed, Feb 18 Topic: Theoretical Evaluation of BT Algortithms
    Required reading:
  • A Theorectical Evaluation of Selected Backtracking Algorithms, by Kondrak and van Beek (IJCAI 1995)
    • Recommended reading: Dechter, Chapters 5 and 6
    Wed, Feb 18 Recitation:
    Discussed class results on Homework 2.
  • Quiz 3
    • Fri, Feb 20 Topic:
  • Evaluating (deterministic) BT Search Algorithms (PPT)
  • Basic Consistency Methods (PPT)
    • Required reading:
  • The complexity of some polynomial network consistency algorithms for constraint satisfaction problems--Mackworth/Freuder
  • Sections 3.1, 3.2, 3.3 of Dechter's book.
    • Recommended reading:
  • Sections 3.4--3.10 of Dechter's book.
  • Networks of Constraints: Fundamental Properties and Application to Picture Processing--Montanari, Information Sciences, 1974. (Retrieve from instructor.)
  • Consistency in networks of relations--Mackworth
  • Constraint propagation with interval labels, E. Davis
  • Path Consistency on Triangulated Constraint Graphs, Bliek, Sam-Haroud, IJCAI 99
    		•
  • List of projects for 2009
    • Week 7
    Mon, Feb 23 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading:Same as above.
  • Homework 3 due
  • Glossary 5 due
  • Homework 4 assigned
  • Glossary 6 assigned
    		•
    Wed, Feb 25 Topic: Same as above.
    Required reading: Same as above.
    Recommended reading: Same as above.
    Wed, Feb 25 Recitation:
    Will take place in Avery Hall 347.     		The Ugrad Math Club: A talk by Dr. Bleak.
    Pizza provided.
    Fri, Feb 27 Topic: TBA
    Required reading: TBA
    Recommended reading: TBA     		Deadline: for project selection. (Use handin.)
    Week 8
    Mon, Mar 2 Topic: Class cancelled, instructor not available.
  • Glossary 6 due
  • Homework 4 due
  • Homework 5 assigned
    		•
    Wed, Mar 4 Topic: Consistency Properties/Methods in CSPs
    Required reading: Dechter Section 3.1--3.3 and 8.1
    Recommended reading: Dechter Chapter 3 and 8, entirely
    Wed, Mar 4 Recitation:
  • Quiz 4
    • Fri, Mar 6 Topic: Same as above
    Required reading: Same as above
    Recommended reading: Same as above
    Week 9
    Mon, Mar 9 Topic: Basic Consistency Properties.
    Required reading: Same as above
    Recommended reading:
  • Dechter Chapter 3, entirely.
    		•
  • Homework 5 due
    		•
    Wed, Mar 11 Topic: Finish Basic Consistency Properties.
    Required reading: Same as above.
    Recommended reading: Same as above.

    Wed, Mar 11 Recitation:
    Talk by Dr. Ben Thengvall of OptTek Systems Inc..
    Title: An Introduction to Simulation Optimization"
    Required reading: The Exploding Domain of Simulation Optimization..
    Fri, Mar 13 Topic:
  • An Efficient Filtering for AllDiff Constraints
    • Required reading:
  • Same as above
  • A Filtering Algorithm for Constraints of Differences in CSPs-- Régin, AAAI 1994.
    • Recommended reading:
  • Dechter Chapter 3, entirely.
    		•
  • Homework 5 due
    		•
    Week 10
    Mon, Mar 16
    Spring vacation
    Wed, Mar 18
    Fri, Mar 20
    Week 11
    Mon, Mar 23 Topic: Finish: An Efficient Filtering for AllDiff Constraints
    Required reading:
  • A Filtering Algorithm for Constraints of Differences in CSPs Régin, AAAI 1994.
    • Recommended reading:
  • Glossary 7 assigned.
    • Wed, Mar 25 Topics: Advanced Consistency Methods
    Required reading: Dechter: Sections 3.1, 3.2, 3.3, 3.4, 3.5.1, 3.5.3, 8.1.
    Recommended reading:
  • Neighborhood Inverse Consistency Preprocessing, Freuder and Elfe AAAI 96
  • Optimal and Suboptimal Singleton Arc Consistency Algorithms, Bessière, Debruyne, IJCAI 2005
  • Domain Filtering Consistencies for Non-Binary Constraints, Bessière, Stergiou, and Walsh, AIJ 2008.
  • Synthesizing constraint expressions, Freuder JACM 1978
    		•
    Wed, Mar 25 Recitation:
  • Quiz 5
    • Fri, Mar 27 Topic: Same as above
    Required reading: Same as above
    Recommended reading: Same as above     		Deadline: Progress reports of projects are due. (Use handin.)
    Week 12
    Mon, Mar 30 Topic: Finish Advanced Consistency Methods
    Start:     Structure-Based Methods, An Introduction
    Required reading:
  • Dechter: Sections 3.1, 3.2, 3.3, 3.4, 3.5.1, 3.5.3, 8.1, and
  • Dechter SectionsL 2.1.3, 4.4, 10.1.1, 9.2, 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.
  • A Sufficient Condition for Backtrack-Free Search, Freuder, JACM 1982
  • A Sufficient Condition for Backtrack-Bounded Search, Freuder, JACM 1985
    		•
  • Glossary 7 due.
  • Homework 6 assigned.

    		•
    Wed, Apr 1 Topic: Structure-Based Methods, An Introduction
    Required reading: Required reading: Dechter Sections: 2.1.3, 4.4, 5.1.2, 10.1.1, 9.2, 9.2.2.
    Recommended reading: Same as above.     		Prof. Dechter is visiting on Apr 2nd, giving a CSE Distinguished Seminar: "Principles for Reasoning with Mixed Probabilistic and Deterministic Graphical Models." (Abstract and Vita)
    Wed, Apr 1 Recitation:
    Lecture by Professor Rina Dechter. Slides of Chapter 4 of textbook.
    Required reading: Dechter's textbook: Chapters 4 and 7
    Fri, Apr 3 Topic: Finish tree search.
    Required reading: TBA
    Recommended reading: TBA
    Week 13
    Mon, Apr 6 Topic: Search Orders in CSPs
    Required reading:
  • Search Orders in CSPs, Chapter 6, Tsang 93
    • Recommended reading:
  • Dechter: Sections: 5.1.1
  • Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems, Geelen 92
    		•
  • Homework 6 due.
  • (Bonus) Homework 7 assigned.
    		•
    Wed, Apr 8 Topic: Same as above
    Required reading: Same as above
    Recommended reading: Same as above
    Wed, Apr 8 Recitation:
    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.     		 
    Fri, Apr 10 Topic: Same as above.
    Required reading: Same as above
    Recommended reading: Same as above
    		 Deadlines: First deadline for extra-credit work. At most 1 paper presentation, 2 summaries, 1 chapter write-up after this date.
    Week 14
    Mon, Apr 13 Topic:
  • Finish above
  • Least Commitment: Rationale and Strategy
  • (If time permits) Advanced Backtrack Search
    • Required reading: For advanced Backtrack Search: ECLiPSe: Chapter 12 on Search (Credit Based Search).
    Recommended reading:
  • 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.
  • (Bonus) Homework 7 due.
    		•
    Wed, Apr 15 Topic: Advanced Backtrack Search
    Required reading: ECLiPSe: Chapter 12 on Search (Credit Based Search).
    		 
    Wed, Apr 15 Recitation:
    Each student must make two statements, questions, remarks, etc. about his her project.     		Corrected HWK 6
    Fri, Apr 17 Topic:
  • Finish Advanced Backtrack Search
  • Start Local Search
    • Required reading: Same as above
    Recommended reading: Same as above
    Week 15
    Mon, Apr 20 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
    		•
    Wed, Apr 22 Topic: Elena will talk about Symmetry in CSPs (PDF slides).
    Required reading: None.
    Recommended reading:
  • Exploiting symmetries within constraint satisfaction search, Meseguer and Torras, AIJ 2001
  • Eliminatring Interchangeable Values in Constraint Satisfaction Problems, Freuder, AAAI 1991.

    • Wed, Apr 22 Recitation:
    Each student must make two statements, questions, remarks, etc. about his her project.     		A quiz may be given in class
    Fri, Apr 24 Class will be held and NOT canceled
    Topic: Temporal Networks (PPT slides)
    Required reading: Dechter, Chapter 12.
    Recommended reading:
  • Manolis Koubarakis, Temporal CSPs, Chapter 19 in the Handbook of CP. 2006
  • R. Dechter, I. Meiri, and J. Pearl, Temporal Constraint Networks. AIJ, Vol. 49, pp. 61-95, 1991
  • I. Meiri, Combining Qualitative and Quantitative Constraints in Temporal Reasoning, 1995
  • Shapiro, Feldman, & Dechter, On the Complexity of Interval-based Constraint Networks, 1999
  • L. Xu & B.Y. Choueiry, Improving Backtrack Search for Solving the TCSP, CP 2003, pp 754-768. 2003
  • L. Xu & B.Y. Choueiry, A New Efficient Algorithm for Solving the Simple Temporal Problem, TIME 2003, pp 212--222
  • B.Y. Choueiry & L. Xu, An Efficient Consistency Algorithm for the Temporal Constraint Satisfaction Problem
    		• Deadlines:
  • Final glossary due, in print and using handin.
  • Project reports are due in print and using handin.
  • Second deadline for extra-credit work: No paper presentation, summaries, write-ups, on or after this date.
    		•
    Week 16
    Mon, Apr 27 Topic: PROJECT DEFENSE
    Attendance is mandatory
    		 Evening sessions if necessary, attendance is optional.
    Wed, Apr 29 Topic: PROJECT DEFENSE
    Attendance is mandatory
    Wed, Apr 29 Recitation from 5:00 to 6:00 pm Topic: PROJECT DEFENSE
    Attendance is mandatory
    		  
    Fri, May 1 Topic: PROJECT DEFENSE
    Attendance is mandatory
    		 Deadline: Project code and slides due, submit using handin.
    Evening sessions if necessary, attendance is optional
    Week 17
    Wed, May 6
    No Final Examination


    Last modified: Fri Nov 13 20:37:34 CST 2009