Fall 2016, CSCE421/821: Course Syllabus
1. General Information
Prereq: CSCE310, Data structures and algorithms or Instructor Permission.
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 119.
Instructor: Prof. Berthe Y. Choueiry
Office location: Room 360, Avery Hall,
Office hours: Wednesday/Friday 4:30--5:30 p.m. or by appointment.
Volunteer Graduate GTA's:
- Daniel Geschwender: Wednesdays 11:00 a.m.--12:00 p.m., Avery Hall 123 (main pod).
- Anthony Schneider: Thursdays 1:00 p.m.--3:00 p.m., Avery Hall 123 (main pod).
- Robert J. Woodward: Thursdays 10:00 a.m.--11:00 p.m., Avery Hall 123 (main pod).
"Constraint Processing" by Rina Dechter,
1st 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
- Islands of tractability for minimality and global consistency.
- Intelligent backtracking.
- Look-ahead techniques.
- Ordering heuristics.
- Theoretical and empirical comparison of hybrid search
- 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.
- 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 at the webpage of the course.
- Course WebPage: You can access all information
about the course from
the course WebPage. Check the course schedule to prepare for each class.
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.
- handin: All homework, projects, reports, etc. must be submitted via the handin 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 syllabus is our
`contract' and we will abide by it.
The course consists of lectures by the instructor, three times per
Required and recommended reading:
As indicated in the Class
schedule. The content of the course will be dynamically
adapted to students interests and performance.
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
- 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
- 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
- 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
- Quizzes cannot be made up.
Tests: There will be a pre-test only. The pre-test cannot
be made up except by instructor's permission.
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
- 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
- Students are responsible for the material covered and
announcements made during the class. Also, there will be surprise
- Bonus points will be awarded to students who attend all
lectures, interact lively, and participate in discussion in class.
- It is the students responsibility to ensure an account on the
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
- Always acknowledge any help received from other
Always fully reference material used (e.g.,
encyclopedia, book, paper, journal, web site).
4. Grading Policy
(Surprise) quizzes: 28%
- Assignments: 40%
- Individual project: 30%. (Research and report:
22%. Presentation: 8%.)
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
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
Give a presentation of a research paper in class: 10% per
presentation. Maximum 2 presentations per
student. One presentation must be made by Friday, Nov 18, 2016, and
one by Friday, Dec 2, 2016.
Critical Summary Write a critical summary of research
papers/topics discussed in class: 5% per summary. Maximum 4 summaries per student. Two summaries must
be submitted by Friday, Nov 18, 2016, and two by Friday, Dec 5,
Write up Write a chapter of a textbook: 20% per
chapter. Maximum 2 chapters per student. One
write-up must be submitted by Friday, Nov 18, 2016, and one by
Friday, Dec 2, 2016.
Attendance A bonus will be awarded to students who attend
all lectures, interact lively, and participate in class
Students who return, every Monday before class, a glossary of terms
listed in handouts will be credited for up to 8% bonus, computed
proportionally to the list of terms they return. Rules for
Students will be have to build an incremental and alphabetically sorted
glossary of important terms.
Terms to be included are the ones listed on the web,
in the handouts distributed in class or sent by 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. Cut-and-pasted from
the web or Wikipedia is not allowed. It will be counted negatively.
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 2,
2016 (Hint: choose a text editor that can sort entries
Participation and feedback If you find errors in the
discussions, respond to challenges, constructively participate in
class discussions, you will be awarded bonus points. A bonus point
will also be given to students who confirm having filled the course
evaluation forms (word of honor).
Closely monitor your grade. If you feel that your grade is slipping,
contact the instructor immediately. We may be able to assign to you
an additional task to put you back on the right track.
7. Books on Reserve at the Math Library in Avery
Constraint Networks, Christophe Lecoutre (e-textbook,
available from UNL's libaries).
Foundations of Constraint Satisfaction by Edward Tsang. Also,
Artificial Intelligence, A Modern Approach (AIMA), by Russell Norvig. Second Edition.
Artificial Intelligence, 3rd Edition. Winston. ISBN 0201533774.
Essentials of Artificial Intelligence. Ginsberg. ISBN 1-558s60-22-6.
Call number Q335.G55 1993.
Artificial Intelligence: A New Synthesis. Nilsson. ISBN 1-55860-535-5.
Call number Q335.N496 1998.
Paradigms of Artificial Intelligence Programming. Norvig. ISBN 1-55860-191-0.
Call number QA76.6.N687.
Artificial Intelligence. Structures and Strategies for Complex Problem Solving.
Luger and Stubblefield
Lisp, The Language, Second Edition. Guy L. Steele, Jr. Digital Press,
LISP, 3rd Edition. Winston & Horn. ISBN 0-201-08319-1.
ANSI Common Lisp; Graham. ISBN 0-13-370875-6.
Paradigms of Artificial Intelligence Programming. Norvig. ISBN 1-55860-191-0.
Call number QA76.6.N687.
Object Oriented Common Lisp. Slade. ISBN 0-13-605940-6
Call number QA76.64 .S576
A mathematical introduction to logic by Enderton, Herbert B,
CALL NO. QA9 .E54 1972.
8. (AI) References
The MIT Encyclopedia of the Cognitive Sciences, call number BF311 .M556
1999, LIB USE ONLY.
Encyclopedia of artificial intelligence, 1992, SECOND EDITION,call number
Q335 .E53, LIB USE ONLY.
"AI Topics" by AAAI
Dictionary of Algorithms, Data Structures,
Online resources (wikipedia) and web search
8. Online Resources
Puzzles Built @ the ConSystLab
Interactive Game of
Set . Built by Amanda Swearngin (2011).
Minesweeper. Built by K. Bayer, J. Snyder, and R. Woodward.
Solver. Built by Ch. Reeson.
CSP Test Instances: In the xml
format of CP Competition.
The list of benchmark problems usually used in the CP
Solvers programming competetion. Check also the related XCSP tools.
The organizers of the International Workshop on Constraint Propagation
and Implementation organize a Solver Competition and make available
the benchmark problems used during the competition. Such as the ones
used in the 2005 competition. Such problem instances are
typically written using the new standards for representing CSP
instances: an XML representation and also a table
(Seems gone for now..) CLib: Configuration Benchmarks Library.
Archives and On-Line Systems
list of Constraint Solvers
Pointers to various generators from the
ConSystlab web page.
Various models of random generators in Java by Bart
ECLiPSe Constraint Logic Programming System
generator in C at LIRMM
generator in Common Lisp by Patrick Prosser (Currently unavailable).
generator in C courtesy of Fahiem
Bacchus (and P. van Run).
JACK: a library providing constraint programming
and search for Java (high-level language, generic search engine, and a
Main publication venues
Constraint Programming (CP),
Journals: AI Journal (index at the Love Library),
Constraints (index at the Love Library, online access).
Constraint Processing Online
Cork Constraint Computation
Centre (4C), Microsoft Research (Cambridge), Monterey Bay
Aquarium Research Institute, PARC, NASA Ames, (to be completed)
Academic Research Groups
Last modified: Sun Aug 21 13:45:18 CDT 2016