CSCE 990-004, Fall 2009: 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: Tuesday 5:00--6:15 pm and Friday 3:00 p.m.--4:15 p.m.
Location: Avery Hall, Room 352.

Instructor:   Prof.  Berthe Y. Choueiry
      Office location: Room 360, Avery Hall,
      choueiry AT cse.unl.edu, tel: (402)472-5444.
      Office hours: Tuesday/Thursday 2:00--3:00 p.m. or by appointment.

GTA:   Mr. Shant Karakashian
      email: shantk AT cse.unl.edu
      Office location: Room 123D, Avery Hall
    

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

For quick response, email cse421@cse.unl.edu.  Your message will be forwarded to both TA and instructor.

Important note: No official GTA was allocated to this class, but Shant has extensive experience in the subject matter and will try to help to the extent possible. All questions will have to be made to the instructor during office hours, make-up class, by email, or by appointment. We will follow a `peer-correction system' by which students grade each other's (glossaries and) homework with the help and close monitoring by the GTA and the instructor.

Topics include but are not restricted to:

Support:

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.

Workload

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:

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:

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.

Attendance

Alerts

3. Grading Policy

Grade Distribution

Grade Conversion

97%

A+

[94, 97[

A

[90, 94[

A-

[87, 90[

B+

[84, 87[

B

[80, 84[

B-

[75, 80[

C+

[67, 75[

C

[60, 67[

C-

[57, 60[

D+

[54, 57[

D

[51, 53[

D-

<=51

F

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, November 20, 2009, and one by Friday, December 4, 2009.

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, November 20, 2009 and two by Friday, December 4, 2009.

Write up

Write a chapter of a textbook: 20% per chapter. Maximum 2 chapters per student. One write-up must be submitted by Friday, November 20, 2009 and one by Friday, December 4, 2009.

Attendance

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

Glossaries

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:

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.

AI

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

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

Logic

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

Conferences:

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

Journals:

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)

Courses

Academic Research Groups

Latex Resources

Last modified: Fri Aug 28 17:36:36 CDT 2009