1. General Information

Prereq: CSCE310, Data structures and algorithms or Instructor Permission.

Course description: Constraint satisfaction has emerged as a powerful approach to articulate and solve many problems in computer science, engineering, and management.  It is now the basis for new programming languages and innovative commercial systems for production scheduling, product configuration, personnel planning and timetabling, etc.  The goal of this course is to prepare students to conduct research in this area. The course will be intensive and will require thorough study of the theory and the algorithms, and a significant implementation effort. Students are expected to be self motivated, and demonstrate intellectual independence and collegial collaboration.

Lectures: Monday, Wednesday, Friday from 3:30 p.m. to 4:20 p.m.
Location: Avery Hall, Room 119.

Make-up Class/Recitation: Monday from 4:30 p.m. to 5:20 p.m.
Location: Avery Hall, Room 110.

Instructor:   Prof.  Berthe Y. Choueiry
      Office location: Room 360, Avery Hall,
      Office hours: Wednesday/Friday 4:30--5:30 p.m. or by appointment.

Graduate GTA's:   Mr.  Robert J. Woodward
      Office hours: Tuesday 5:00--6:00 p.m., held in Avery Hall 13A (Student Resource Center) or by appointment.

Textbook:
"Constraint Processing" by Rina Dechter, 1^st edition. The textbook will not be followed sequestially, but should be used for reference.

Topics include but are not restricted to:

• Properties, computational complexity, and practical importance.
• Global and local consistency: algorithms, properties and computational complexity.
• Islands of tractability for minimality and global consistency.
• Intelligent backtracking.
• Look-ahead techniques.
• Ordering heuristics.
• Theoretical and empirical comparison of hybrid search algorithms.
• Phase transition.
• Modeling and reduction methods between representations.
• If time permits: Decomposition. Symmetries and their approximations. Temporal constraint networks. Stochastic search. Reformulation and abstraction. Dynamic/conditional Constraint Satisfaction (CSP). Constrained Optimization Problem (COP).
• Other, depending on class interests.

Support:

• Rina Dechter, Constraint Processing, 2003, Morgan Kauffmann.  Available from bookstore.
• Edward Tsang, Foundations of Constraint Satisfaction. Available from instructor and on reserve at the Math Library in Avery.
• Technical papers given by instructor or available from the Electronic Reserve at the Love Library.

2. Communications

• Course WebPage: You can access all information about the course from the course WebPage. Check the course schedule to prepare for each class.
• Blackboad: Grades are posted on Blackboard. Check them regularly and alert us about grading errors within 7 calendar days.
• Piazza: For a quick response, send your questions to Piazza. Your message will be read by the TA and the instructor and they will respond to you ASAP.
• Webhandin: All homework, projects, reports, etc. must be submitted via the webhandin system of CSE.
• Wiki: You can upload the Excel file of the results of your homework on the wiki and check the results of others so that you can debug your code.
• Anonymous Suggestion Box: You may also choose to drop us a note in the Anonymous Suggestion Box to express any opinion about the course. (You can do it also via Piazza.)

3. Protocol of the Course

The course consists of lectures by the instructor, three times per week.

Workload

Required and recommended reading:

Programming, theoretical, and library-search assignments:

• Programming assignments homework must be turned in using the web handin program on cse.unl.edu and turned in before class on the due date.
• Pen-and-paper assignments must be given to the instructor right before the lecture on the due date.
• Late homeworks are subject to a 20% deduction per day (including week-ends), any second after the due date counts as an entire day.
• Programming assignments can be done in Java, C, C++ and must run on cse. If you would like to use another programming language, please clear it out first with the instructor.
• When code and data structures are provided for guidance, they will be mostly in Common Lisp (advice: use Allegro Common Lisp on Linux or a sun workstation).
• Students are kindly requested to indicate how much time they approximately spend on each exercise; this information will be aggregated and used for planning purposes and to balance your workload: it does not affect grading and the evaluation of individuals.

Surprise quizzes:

• There will be surprise quizzes throughout the semester (with a frequency inversely proportional to students' attendance).
• Quizzes will address all material covered during the lectures and/or by the required reading.
• No books or personal notes are allowed during the quizzes, unless explicitly specified.
• Quizzes cannot be made up.

Tests:

Project research, report, and presentation:

• The project can be either a literature study/survey or the implementation of algorithms.
• A presentation to the class is mandatory. The grade will take into account the quality of the research, report, and presentation.

Attendance

• Because the course heavily relies on class discussion, attendance is mandatory.
• Attendance is taken at every lecture.
• Students who miss more than four sessions including make-up class/recitation may be asked to leave the course.
• Advanced notice to the instructor for each absence is required.
• Students are responsible for the material covered and announcements made during the class. Also, there will be surprise quizzes.
• Bonus points will be awarded to students who attend all lectures, interact lively, and participate in discussion in class.

Alerts

• It is the students responsibility to ensure an account on the department's computers.
• Discussions among students, instructor, and TA are encouraged. Homework however are a strictly individual activity: no sharing is permitted (unless when specified by instructor). Unethical behavior will be heavily sanctioned (e.g., a null grade on the task or an F grade on the course).
• Always acknowledge any help received from other individuals.
• Always fully reference material used (e.g., encyclopedia, book, paper, journal, web site).

4. Grading Policy

Grade Distribution

• Pre-test: 2%
• (Surprise) quizzes: 28%
• Assignments: 40%
• Individual project: 30%.  (Research and report: 22%. Presentation: 8%.)

Grade Conversion

Reminder from the College of Arts & Sciences: a C (2.0) is the minimum passing grade in a PASS/NO PASS course (NOT a C-) as well as the lowest grade one can receive and still count the class toward a major.

5. Department and University Policies

The Student Resource Center is located in Avery 13A. It is a valuable place to go for general CSE related issues.

It is CSE Department policy that all students in CSE courses are expected to regularly check their email so they do not miss important announcements.

All homework assignments, quizzes, exams, etc. must be your own work. No direct collaboration with fellow students, past or current, is allowed unless otherwise stated. The Computer Science & Engineering department has an Academic Integrity Policy. All students enrolled in any computer science course are bound by this policy. You are expected to read, understand, and follow this policy. Violations will be dealt with on a case by case basis and may result in a failing assignment or a failing grade for the course itself.

The CSE Department has an anonymous suggestion box that you may use to voice your concerns about any problems in the course or department if you do not wish to be identified.

Students with disabilities are encouraged to contact the instructor or teaching assistant for a confidential discussion of their individual needs for academic accommodation. It is the policy of the University of Nebraska-Lincoln to provide flexible and individualized accommodations to students with documented disabilities that may affect their ability to fully participate in course activities or to meet course requirements. To receive accommodation services, students must be registered with the Services for Students with Disabilities (SSD) office, 132 Canfield Administration, 472-3787 voice or TTY.

6. How to Secure a Good Final Grade

Make a Presentation

Critical Summary

Write up

Attendance

Glossaries

• Students will be have to build an incremental and alphabetically sorted glossary of important terms.
• Terms to be included are the ones listed in the handouts distributed in class or sent my email.
• A glossary entry can be filled with: (1) its definition in Dechter's textbook, (2) its definition from another AI textbook, dictionary, or web resource, or (3) the student's own interpretation.
• All terms encountered during a week are due as a weekly glossary the following Monday, or as indicated in the schedule of the class.
• At the end of the course, the full alphabetically sorted glossary is due. The deadline for submitting final glossary is Friday, December 5, 2014 (Hint: choose a text editor that can sort entries alphabetically.)

Participation and feedback

Additional Work

7. Books on Reserve at the Math Library in Avery

Constraint Processing

AI

Lisp

Logic

8. (AI) References

8. Online Resources

Puzzles Built @ the ConSystLab

Benchmark Problems

Archives and On-Line Systems

Main publication venues

Conferences:

Journals:

Constraint Processing Online

• Association for Constraint Programming
• CP Online
• Yahoo Group: Constraints, Association for Constraint Programming
• AI Topics of the American Association for Artificial Intelligence, etc.

Research Centers

Courses

• Rina Dechter: Constraint Networks ( 1999, 2001, 2003, 2007, 2010, 2014)
• Michela Milano: Constraint Programming Approach to AI Applications
• Roman Barták:
  • Foundations of Constraint Satisfaction, ESSLI 2002
  • Constraint Programming: An Online Textbook.
• Fahiem Bacchus: CSC2512F Constraint Satisfaction Problems
• Barbara Smith: Tutorial on Constraint Programming (PS, PDF).
• David McAllester: Lecture notes.
• Bacchus' Constraint Programming Bibliography

Academic Research Groups

• Constraint Systems Laboratory at UNL
• LIA@EPFL
• Cork Constraint Computation Centre (4C) of Freuder in University College Cork, Ireland.

Latex Resources

• More resources on the web page of the course (Online resources)
• From Shant Karakashian: LaTeX on Wikibooks
• From Joel Gompert: Getting memory-efficient, pretty-looking, robust graphics with very fancy robust labels into LaTeX
• From Ryan Lim: The not so short introduction to LaTex