CSCE421/821, Spring 2011: Course Syllabus

1. General Information

Prereq: CSCE235, Discrete Math (exceptionally this year).

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 course will review the foundations of constraint satisfaction and the basic mechanisms for constraint propagation.  It will cover aspects of modeling and representation, and will examine islands of tractability and methods for theoretical and empirical evaluation of problem `difficulty.'  If time permits, we will examine new methods for decomposition and symmetry identification, designed to overcome the complexity barrier and to support interactions with users.

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

Make-up Class/Recitation: Monday from 5:00 p.m. to 5:50 p.m.
Location: Avery Hall, Room 111 (moved from AvH 20).

Instructor:   Prof.  Berthe Y. Choueiry
      Office location: Room 360, Avery Hall,
      choueiry AT, tel: (402)472-5444.
      Office hours: Wednesday/Friday 3:30--4:30 p.m. or by appointment.

Volunteer GTA's:
      Mr. Shant Karakashian
      email: shantk AT
      Office hours held in Student Resource Center.
      Hours: Thursday: 9:00 a.m. -- 11:00 a.m.
      Also by appointment

      Mr. Robert Woodward
      email: rwoodwar AT
      Office hours held in Student Resource Center.
      Hours: Thursday: 5:00 p.m. -- 6:00 p.m. & Friday 9:00 a.m. -- 10:00 a.m.
      Also by appointment

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

For quick response, email  Your message will be forwarded to the GTA's and instructor and answered by the first person available.

Important note: No official GTA was allocated to this class. We may have a UTA (undergraduate TA) with likely little experience in the subject matter and who will mainly help with administrative matters. Shant and Robert have extensive experience in the subject matter and will try to help to the extent possible. They are both volunteers: It is thus best to talk to them during their office hours. Please send all questions to cse421 AT for a quick response.

Topics include but are not restricted to:


2. 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 week.


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:

Surprise quizzes:


There will be a pre-test only. The pre-test cannot be made up except by instructor's permission.

Project research, report, and presentation:

Search Competition:

One of the projects is a search competition to solve a real-worl problem. Students will receive code and data that model a real-world application, all in LISP. Students will choose some search mechanism and implement it in the language of their choice. Results will be compared, winner will receive a gift certificate for a book.



3. Grading Policy

Grade Distribution

Grade Conversion



[94, 97[


[90, 94[


[87, 90[


[84, 87[


[80, 84[


[75, 80[


[67, 75[


[60, 67[


[57, 60[


[54, 57[


[51, 53[




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.

4. 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 April 9, 2011, and one by Friday, April 22, 2011.

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, April 9, 2011 and two by Friday, April 22, 2011.

Write up

Write a chapter of a textbook: 20% per chapter. Maximum 2 chapters per student. One write-up must be submitted by Friday, April 9, 2011 and one by Friday, April 22, 2011.


A bonus will be awarded to students who attend all lectures, interact lively, and participate in class discussions.


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 glossary:

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).

Additional Work

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.

5. Books on Reserve at the Math Library in Avery

Constraint Processing

Foundations of Constraint Satisfaction by Edward Tsang.


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


Common Lisp, The Language, Second Edition. Guy L. Steele, Jr. Digital Press, ISBN: 1555580416
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.

6. (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.
Section on "General AI Information" in "AI Resources."
Dictionary of Algorithms, Data Structures, and Problems
Online resources (wikipedia) and web search engines (Google, Altavista, etc.)

7. Online Resources

Puzzles Built @ the ConSystLab

Interactive Minesweeper. Built by K. Bayer, J. Snyder, and R. Woodward.
Interactive Sudoku Solver. Built by Ch. Reeson.

Benchmark Problems

Coloring Australia map: In the xml format of CP Competition (courtesy of Ken Bayer).
The list of benchmark problems usually used in the CP Solvers programming competetion. Check also the related 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 representation.
(Seems gone for now..) CLib: Configuration Benchmarks Library.

Archives and On-Line Systems

A list of Constraint Solvers
Pointers to various generators from the ConSystlab web page.
Various models of random generators in Java by Bart Craenen
The ECLiPSe Constraint Logic Programming System
Random generator in C at LIRMM
Random generator in Common Lisp by Patrick Prosser
Random 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 visualization tool).

Main publication venues


Constraint Programming (CP), AAAI, IJCAI, ECAI, FLAIRS, etc.


AI Journal (index at the Love Library), Constraints (index at the Love Library, online access).

Constraint Processing Online

Research Centers

Cork Constraint Computation Center (4C), Microsoft Research (Cambridge), Monterey Bay Aquarium Research Institute, PARC, NASA Ames, (to be completed)


Academic Research Groups

Latex Resources

Last modified: Tue Jan 18 12:04:24 CST 2011