CSCE990-06, Spring 2003: Advanced Constraint Processing

Course description: This course is a continuation of the course on Foundations of Constraint Processing (CSCE 821). It is intended for students with some sophistication and considerable interest in exploring methods of designing and using algorithms useful for solving combinatorial problems. The goal of the course will be to study, analyze and critique basic and current research papers and to engage in Constraint Processing projects and experiments either alone or in small groups.
    Topics may include (and are not restricted to)

non-binary constraints,

over-constrained problems,

temporal reasoning,

symmetry and interchangeability,

continuous CSPs,

distributed constraint satisfaction,

constraints in relational databases,

spatial reasoning, etc.

Time:                 Monday, Wednesday, from  2:30 to 3:45 p.m.

Place:                 CBA 104 (room changed on January 22, 2003)

Instructor:      Prof. Berthe Y. Choueiry
                            Room 104, Ferguson Hall
                            choueiry@cse.unl.edu
                            Tel: (402)472-5444

Office hours:   Monday, Wednesday 3:45--4:45 p.m.  or by appointment

Important:      Regularly check out the page of class schedule for reference to required and recommended reading material, homework texts, and announcements.

Protocol of the course:

Study of selective chapters of the manuscript on Constraint Processing by Rina Dechter.

Mainly discussions of technical papers, otherwise lectures by the instructor and presentations by students.

Absence:  maximum 3 sessions, advanced notice required.

Collaboration and discussion within and outside the classroom strongly encouraged unless specified (e.g., for assignments, quizzes, or riddles').

• Students will be able to `compose' their grade, for up to 80% of the total grade, from the following menu:
• Presentation of a research paper  by a student: 20%. Grading policy will be given by instructor.
• Scribe of a discussion topic or a paper presentation or a critical summary of a research paper: 5%.  A student takes notes of an entire discussion of a topic. One or more other students criticize the notes of the scribe and rate the minutes (Excellent, Good, Satisfactory, or Poor).
• Project (programming): 30%
• Term paper: 30%.
• The remaining 20% are allocated as follows:
• Surprise quizzes (mainly) and assignments (minimal): 10%.
• Class interaction and participation in discussions are (subjectively) evaluated for 10% of the total grade.

• A bonus will be offered for a 100% attendance, starting second week of semester.
• Do the weekly and final glossaries: 5% (total).  Students who return every Monday, before class a glossary of terms listed in handouts will receive

a bonus.   Rules for glossary:
• 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 AIMA, (2) its definition from another AI textbook or dictionary, or (3) the student own interpretation.
• All terms encountered during a week are due as a weekly glossary the following Monday.
• At the end of the course, the full alphabetically sorted glossary is due. (Hint:  choose a text editor that can sort entries alphabetically.)

Textbooks:

Main AI textbooks are available on reserve for CSCE 476/876 at the Love Library (but you are welcome to check them out):
AI:

• Artificial Intelligence, A Modern Approach (AIMA), by Russell & Norvig.
• 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: Theory and Practice. Thomas Dean, James Allen, and Yiannis Alomonos. Addison-Wesley, 1995. Available from instructor.

• LISP, 3rd Edition. Winston & Horn. ISBN 0-201-08319-1.
• ANSI Common Lisp, Paul Graham. ISBN 0-13-370875-6.
• Paradigms of Artificial Intelligence Programming. Norvig. ISBN 1-55860-191-0. Call number QA76.6.N687.

• Intelligent Planning: A Decomposition and Abstraction Based Approach. Qiang Yang. Springer-Verlag, 1997. Call Number Q334 .Y36 1997 .
• A mathematical introduction to logic by Enderton, Herbert B, CALL NO. QA9 .E54 1972.

• LIA@EPFL
• APES Group in the UK.
• Constraint Computation Center of Freuder in Univ. of New Hampshire.
• Cork Constraint Computation Center (4C) of Freuder in University College Cork, Ireland.

• Random generator in Java by Zheying Yang (zyang@cse.unl.edu)
• Links to Constratint Solvers, via the CSPLIB
• The ECLiPSe Constraint Logic Programming System
• Constraints archives at CCC.
• CSPLib: Problem Library on the Web.
• 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).

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