CSE 352
Spring 2003
Stony Brook
Artificial Intelligence
Annie Liu
Assignment 5
Handout A5
Mar. 11, 2003
Due Mar. 25


Programming with Logical Relations and Rules

Your task is to solve a number of problems using logical relations and rules and implement them using XSB, a well-known tabled Prolog implementation that happens to be developed at Stony Brook. :-) You can download XSB from xsb.sourceforge.net. Remember that programming assignments are to be done in pairs; if you didn't have a partner for previous assignments, you are encouraged to have one this time.

You should write down your code before you sit at the terminal. All your code should be put in one file and be well-commented or clearly self-explanatory. You should also provide code for testing your programs as automatically as possible and include instructions for demo/testing.

Submission

Submit a printout of the following items in class on the due date, preferably printed 2 pages per sheet.

  1. Your code, well-commented or clearly self-explanatory.
  2. A trace of running each program on sample data of your choice. Make sure to print out the input data, the query, and the query results.
Email cse352ATcsDOTsunysbDOTedu before that a .zip file that contains all your code and documents.

Grading

This homework is worth 5% of the course grade. Exceptionally well-thought-out and well-written homeworks will receive appropriate extra credit. Partial solutions get partial credit, but if you only manage to write some of the components, you should test each of them and hand in the results of the test.

Problems

  1. Graph algorithms.

    Given a graph, the transitive closure of its set of edges is the set of pairs (n1,n2) such that there is a path from n1 to n2 following the edges. We can use binary relation edge for the set of edges, and define relation path as follows.

      path(X,Y) :- edge(X,Y).
      path(X,Y) :- path(X,Z), edge(Z,Y).
    
    Then, the query ?- path(X,Y) will return the transitive closure.

    Suppose that, in addition to the graph, we are given a set of nodes as sources. You can use a unary relation for the given set of source nodes. You are asked to define, in two ways as described below, a unary relation reach such that reach(X) is true if and only if X is reachable from a source node following zero or more edges.

    (a) Define the relation using path.
    (b) Define the relation without using path.

    Note that both programs can get into infinite loop and have repeated computations of the same goal, if run using naive backtracking, as described in lecture and in textbook. However, if you specify

      :- table path/2.
      :- table reach/1.
    
    in XSB (the numbers 2 and 1 indicate the number of arguments of the relations), both will terminate and be very efficient.

  2. Database queries.

    Our "Solarlet" course database has relation course relating four items: a name, a lecturer, a time, and a place, where time is composed of a day, a starting time, and a finish time. That is, the relation is of the form course(Course,Lecturer,Time,Place), where Time is a compound object of the form time(Day,Start,Finish).

    We can use rules to define particular relations of interest, such as lecturer, duration, teaches, and occupied below.

      lecturer(Lecturer,Course) :-
        course(Course,Lecturer,Time,Place).
    
      duration(Course,Length) :-
        course(Course,Lecturer,time(Day,Start,Finish),Place),
        Length is Finish-Start.
    
      teaches(Lecturer,Day) :-
        course(Course,Lecturer,time(Day,Start,Finish),Place).
    
      occupied(Place,Day,Time) :-
        course(Course,Lecturer,time(Day,Start,Finish),Place),
        Start<=Time, Time<=Finish.
    

    (a) Add rules defining the relations location(Course, Building), busy(Lecturer,Time), and cannot_meet(Lecturer1,Lecturer2).
    (b) Possibly using relations from (1), define the relation schedule_conflict(Time,Place,Course1,Course2).

  3. Sorting programs.

    Exercise 9.14 of textbook. This is for programming permutation sort and insertion sort. You are not required to write a quick sort, but if you do, you get upto 20% bonus for this assignment.

  4. Algebraic rewrite.

    Exercise 9.15 of textbook. This is for algebraic simplification as well as symbolic differentiation as we did in Assignment 2. This kind of symbolic manipulation is much easier in Prolog.