CSE505 (Spring 2024)
Computing with Logic

General Information | Schedule | Resources | Requirements

General Information

Course description: This course is for students interested in learning the power of programming with logic, especially high-level logic rules, efficient implementations, and diverse applications.

We will study logic languages as tools for expressing knowledge and queries, as well as solution strategies, for complex application problems, and study systems that implement these languages for efficiently solving the problems. We will also discuss computing with logic at large for reasoning and learning with uncertainty, including for explainable AI.

The course will touch on a variety of powerful languages and systems. Rather than dwell on the features of any particular language, we will focus instead on understanding the commonalities and differences among languages, the reasons for them, and the implications of them in applications.

Prerequisites: Undergraduate discrete math with good analytical experience (predicate logic, sets, functions, relations, probability) plus good experience with commonly-used programming languages and algorithms. | Credits: 3 | Official course information

Instructor: Annie Liu | Office: New CS 237 | Phone: 631-632-8463 | Email: liu@cs.stonybrook.edu | Office hours: Mon 4:20-5 PM, Tue 11:20-12 PM, Thu 11:20-11:40 AM, 2-3 PM, or email for an appointment.

TA: Geoffrey Churchill | TA Office: CS 2126 | Email: Geoffrey.Churchill@stonybrook.edu | Office hours: Wed 1-3 PM, Fri 12-1 PM.

Lectures: Tue Thu 10-11:20 AM, New CS 120.

Textbook: There is no required textbook for this course; best relevant book chapters, lecture notes, and/or slides will be given under resources as the course proceeds.

Grading: Lecture critiques: 5% | Lecture notes: 10% | In-class exercises: 10% | Assignments: 10% | 2 Quizzes: 2 x 15% | Course project: 35% | No late submission will receive credit.

Course homepage: http://www.cs.stonybrook.edu/~liu/cse505/

Schedule

 
14 weeks total for 4 units, including 2 quizzes

Unit 1: Overview and preparation - 2 weeks (1/23-)

  An overview of the course, and a brief review of logic in imperative
  programming, database programming, and functional programming.

  This will especially include programming with sets, relations, and
  predicate logic; programming with recursive functions; and a systematic
  method for algorithm design and program optimization.

    Tue 1/30 Project problem interest due
    Tue 2/6  Project problem interest update due


Unit 2: Programming with logic - 6 weeks (2/6-)

  Programming with logic rules and constraints, including key features of
  logic languages and main methods of their implementations.

  This will study programming in a wide variety of logic languages: (1)
  Datalog, the core of logic rules; (2) Prolog and answer-set programming
  (ASP), two main families of logic languages; and (3) languages supporting
  combined, more advanced, and/or more specialized features. We will also
  discuss constraint programming (CP) and mathematical programming (MP)
  that are closely related to logic programming (LP).

  The study will include how programs in these languages work: bottom-up
  inference starting from given facts, top-down search driven/directed by
  the queries/goals, grounding, backtracking, backjumping, tabling,
  indexing, and demand transformation.

  We will also see how some logic languages and systems support multiple
  paradigms/models of programming and problem solving. For example, Prolog
  supports logic programming as well as relational programming, recursive
  programming, and procedural programming; and ErgoAI supports also
  objects and transactional updates.

    Tue 2/6  Assignment 1
    Fri 2/23 Assignment 1 due

    Fri 2/23 Assignment 2
    Fri 3/8  Assignment 2 due

    Sun 3/10 Project design and test program due

        3/11-17 Spring break week

    Tue 3/19 Quiz 1 preparation
    Thu 3/21 Quiz 1, in class


Unit 3: Computing with logic at large - 5 weeks (3/26-)

  Computing with logic and probability, for knowledge representation,
  reasoning, and learning.

  This will include (1) knowledge representation using circuits and rules
  extended with probabilities and/or weights; (2) efficient inference with
  optimized decision diagrams; (3) and learning of the circuit structures
  and parameters/weights as well as learning of rules.

  We will also see how logic with probability provides a rigorous
  foundation for explainable AI, with efficient and exact inference for a
  wide range of complex reasoning and learning tasks.

    Fri 4/19 Project prototype due
    Thu 4/25 Quiz 2


Unit 4: Review and outlook - 1 week (4/30-)

  Revisiting the challenges of programming with logic rules and queries for
  konwledge representation, reasoning, and learning, and envisioning what's
  to come.

  This will include a unified, simple, yet more powerful logic rule
  language for ease of use by everyday users.

    Fri 5/3 Project due
    Tue 5/7 Project presentations, during final exam time 8-10:45 AM

Resources

Google Classroom for this course, for students in the course

Requirements

Follow all information in the Google Classroom for this course.

Attend all lectures and take good notes. This is the most efficient way to learn the course materials, because we will both distill and elaborate written materials and discuss important related materials. We will start promptly on time. We will have every student participate in solving problems and presenting solutions in class.

Do all course work. The readings are to help you preview and review the materials discussed in the lectures. The assignments and project are to provide concrete experiences with the basic concepts and methods covered in the lectures. The exercises are to help check that you are keeping up with the lectures and the assignments. The quizzes will be comprehensive.

If you have any questions, ask. Ask questions in class, in office hours, and in the Q&A group. Talk with your classmates, and share ideas, but not solutions to assignments.

Your submitted work

Your handins must include the following information at the top: your name, student id, course number, assignment number, and due date, and must be submitted in a neat and organized fashion.

Your programming solutions must be submitted with a README.txt file explaining where things are, what you did and found for the assignment (that is not described in the assignment handout), and how to run and test your program. This file is worth a non-trivial portion of the grade.

Your approach to solving problems is as important as your final solutions; you need to show how you arrived at your solutions and include appropriate explanations. Always include good explanations in your README file and good comments in your code.

Your assignment and project submissions must be your own work. You are not permitted to share, borrow, or even look at another student's work while completing your own assignment. Likewise, copying material from any source other than what is specified by the instructor will constitute cheating. You may discuss ideas with others and look up references, but you must write up your solutions independently and credit all sources that you used. Any evidence that answers have been copied, shared, or transmitted in any way, including the use of answers downloaded from the Internet or written by others previously, will be regarded as evidence of academic dishonesty. Anyone involved will be reported.

Submission issues

Neither extensions nor late submissions will be approved under normal circumstances. If some emergency or other circumstances truly beyond your control prevent you from submitting your assignment on time, supply the instructor with suitable documentation and notification prior to the assignment deadline. The instructor will also refer you to the Dean of Students for follow-up consultation.

Students are urged to plan ahead to avoid problems such as computer failures at the last minute. If your assignment is incomplete before it is due, turn in whatever you have. You are advised to budget your time wisely and to start working on an assignment the day it is posted.

Grading issues

The final grade you receive in this class will reflect, as far as possible, the extent to which you have mastered the concepts and their applications. How much someone needs a grade, or how close they are to the next higher grade, will have no effect on grade. As the instructor, I want everyone to do well in this course, and will make every reasonable effort to help you understand the material taught. However, the grades provided at the end of the semester are final, except for rare situations involving grading errors. They will not be altered for other reasons, so please do not ask me to do so.

If you think you found grading errors, please arrange a re-grading within one week of receiving the graded work; later requests will not be entertained.

To promote consistency of grading, issues about work graded by a TA should be addressed first to the TA and then, if the issues are not resolved, to the instructor.

University Policies

Academic Integrity

Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Faculty is required to report any suspected instances of academic dishonesty to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty please refer to the academic judiciary website at http://www.stonybrook.edu/commcms/academic_integrity/index.html

Student Accessibility Support Center

If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact the Student Accessibility Support Center, Stony Brook Union Suite 107, (631) 632-6748, or at sasc@stonybrook.edu. They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential.

Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and the Student Accessibility Support Center. For procedures and information go to the following website: https://ehs.stonybrook.edu/programs/fire-safety/emergency-evacuation/evacuation-guide-disabilities and search Fire Safety and Evacuation and Disabilities.

Critical Incident Management

Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of Student Conduct and Community Standards any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn. Further information about most academic matters can be found in the Undergraduate Bulletin, the Undergraduate Class Schedule, and the Faculty-Employee Handbook.

Computer Science Department Policies and Procedures Governing Graduate Academic Dishonesty
Annie Liu