Course Syllabus

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

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

Instructor:   Prof.  Berthe Y. Choueiry
      Office location: Room 259, Avery Hall,
      Office hours: Monday/Friday 4:30--5:30 p.m. 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 at the webpage of the course.

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.
• Canvas: Grades are posted on Canvas. 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 instructor who 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 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.
  


• Homework:
  • Homework include programming, theoretical (pen and paper), 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.


• Quizzes:
  • There will a quiz every week. Cancellation are announced on the class schedule.
  • Quizzes address all material covered during the lectures, required reading, and/or homework.
  • Questions on the quiz may include material starting from where the previous quiz covered until the material covered on the day before the current quiz.
  • No books or personal notes are allowed during the quizzes, unless explicitly specified.
  • Quizzes cannot be made up.


• Tests:
  • There will be only a pre-test, i.e., no midterm, no final.
  • The goal of the prestest is to alert you about the extent of the pre-requisite knowledge that you need to have to succeed in this course.
  • The pre-test cannot be made up except by instructor's permission.


• Class participation: Glossaries are lists of important terms that students should be able to define formally. After finishing a topic, we will go through the terms in the the corresponding glossary and state these definitions as formally as possible. Students who can correctly define a term earn a bonus point towards class participation. These bonus points are cumulated and constitute the 8% component of the grade.


• Project research, report, and presentation: Given the dense form of the semester, there will be no project in this course this semester. If you are interested in doing an additional project, please contact the instructor.

Attendance

• Because the course heavily relies on class discussion, attendance is mandatory.
• Students who miss more than six 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.

Alerts

• It is the students responsibility to ensure an account on the department's computers (cse).
• Discussions among students and with instructor 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).

No Class Recording

Any work and/or communication that you are privy to as a member of this course should be treated as the intellectual property of the speaker/creator. It is not to be shared outside the context of this course. Students may not make or distribute screen captures, audio/video recordings of, or livestream, any class-related activity, including lectures and presentations, without express prior written consent from me or an approved accommodation from Services for Students with Disabilities. If you have, or think you may have, a disability such that you need to record or tape class-related activities, you should contact Services for Students with Disabilities. If you have an accommodation to record class-related activities, those recordings may not be shared with any other student, whether in this course or not, or with any other person or on any other platform. Failure to follow this policy on recording or distributing class-related activities may subject you to discipline under the Student Code of Conduct.

4. Grading Policy

Grade Distribution

• Pre-test: 2%
• Class partipation: 8% (typically discussion of glossary terms during recitation)
• Quizzes: 40%
• Assignments: 50%

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.

5. How to Secure a Good Final Grade

• 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, March 26, 2021
  • Two summaries must be submitted by Friday, April 23, 2021.



• Bonus points will be awarded for class participation (e.g., asking good questions, answering challenging questions, and helping other students).


• Submitting a course evaluation A bonus point will be awarded to students who confirm having filled the course evaluation forms (word of honor).

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

UNL offers a variety of options to students to aid them in dealing with stress and adversity. Counseling and Psychological Services (CAPS) is a multidisciplinary team of psychologists and counselors that works collaboratively with Nebraska students to help them explore their feelings and thoughts and learn helpful ways to improve their mental, psychological and emotional well-being when issues arise. CAPS can be reached by calling 402-472-7450. Big Red Resilience & Well-Being provides fun events, innovative education, and dynamic services to help students understand emotions, manage stress, build strength, connect with others, develop grit and navigate transitions.

7. Books on Reserve at the Math Library in Avery

Alert: Subject to opening hours and policies of UNL Libraries, especially during pandemic.

Constraint Processing

Constraint Networks, Christophe Lecoutre (e-textbook, available from UNL's libaries).
Foundations of Constraint Satisfaction by Edward Tsang. Also, available online.

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.

(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, and Problems
Online resources (wikipedia) and web search engines.

8. Online Resources

• Puzzles Built @ the ConSystLab
  Interactive Game of Set . Built by Amanda Swearngin (2011).
  Interactive Minesweeper. Built by K. Bayer, J. Snyder, and R. Woodward.
  Interactive Sudoku Solver. Built by Ian Howell on an initial project by Ch. Reeson.
  


• Benchmark Problems
  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 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 (Currently unavailable).
  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, ISAIM, etc.
  • Journals: AI Journal (index at the Love Library), Constraints (index at the Love Library, online access).
  
  
• Constraint Processing Online:
  • Association for Constraint Programming
  • AI Topics of the American Association for Artificial Intelligence, etc.


• CP 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


• 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