CP3210 Prolog Assignment, 1999

Worth 25%. Due on 20/5/99 (Thursday, preferably at the Tutorial).

Your Prolog Assignment consists of the following 4 problems (problems 1, 2 and 3 carry 5 marks each and problem 4 carries 10 marks):

FACTS: Build a time-tabling database containing facts about (a) student enrollment -- each fact is of the form enrolled(student,subject, semester), (b) subjects offered by various schools -- each fact is of the form school(subject,school) and (c) scheduling of various subjects -- each fact is of the form scheduled(subject,semester,time,room) and ask the following queries.
1. Is Mary enrolled in CP3210 ?
2. Is Mathew enrolled in a subject offered by CMP ?
3. Is there anyone who enrolled in the same subject both in first semester as well as second semester ?
4. Is room MP101 being used for 3 consecutive hours ?
5. Is there any student with a time-table clash (enrolled in 2 subjects scheduled for the same time) ?
FACTS-and-RULES: Run programs given in the class room for (1) member, (2) append, (3) delete, (4) insert (5) append-last, (6) quick-sort, (7) merge-sort, (8) list-length, (9) list-product, (10) dot-product, (11) permutation, (12) reverse (13) can-go and (14) sublist with queries that contain variables like ?- member(X, [a,b,c,d]) and ?- member(X, [a,b,X,d]) and ?- member([maison,X], [[voiture,car] [pelouse,lawn] [maison,house]|Z]).
EXPRESSION-MANIPULATION: Write a program that computes the derivatives of expressions containing plus, minus, times and power operators. The query ?- derivative(expression1, variableX, expression2) returns `yes' if expression2 is the derivative of expression1 with respect to variableX. Demonstrate your program works by answering a few sensible queires computing derivatives of expressions containing plus, minus, times and power operators.

SEARCH: This problem consists of 2 parts:

Implement the generic search algorithm and variate it to implement (a) Depth-First Search, (b) Breadth-First Search, (c) Branch-and-Bound, (d) Best-First Search, (e) Heuristic Depth-First Search and (f) A* algorithm. Run them on the following graph (note: for non-horizontal edges, * denotes the head and the number near an edge is its cost). Use 3 heuristic functions: h1(n) = distance of Goal from n, h2(n) = distance of n from Start and h3(n) = distance of Goal from n minus 1.

                         8        4          5 
                    d ------> e ------> n -------> o 
                   *           \                  / *
                  /           2 \              1 /   \
               4 /               \              /   1 \
          3     /      16         *     5      *       \    3
  Start -----> b ----------------> g -------> m         s -----> t
              / \                 *          * \       *         |
           1 /   \             2 /          /   \   1 /        2 |
            /   3 \             /        2 /   1 \   /           |
           *       *    7      /   5      /       * /     5      *
           i        c ------> f ------> v          p ----------> u
          / \        *        |        *           *              \
       1 /   \        \       |       /            |               \ 2
        /   1 \        \    1 |    3 /             |                \
       *       *        \     |     /              |                 *
       j       k       1 \    |    /             3 |                Goal
                          \   |   /                |
                           \  |  /                 |
                            \ * /   2        2     |
                              h -------> q ------> r

Run your programs for (a) Depth-First Search, (b) Breadth-First Search, (c) Branch-and-Bound, (d) Best-First Search, (e) Heuristic Depth-First Search and (f) A* algorithm to find out a path from a given Start node to a given Goal node in a 9 x 9 grid given a list of (dangerous) tiles to be avoided on the path. (Hint 1: Your graph is not completely defined in the program, but a part is defined in the query. Your program may assume that an agent can move north/south/east/westward from any tile. Query will tell which tiles are to be avoided. Hint 2: Use predicate `legal'). Use 3 heuristic functions: h1(n) = horizontal distance of Goal from n, h2(n) = vertical distance of n from Start and h3(n) = average of h1(n) and h2(n).

A GRACELESS GRACE: *(This an extra problem carrying 3 marks. Marks obtained for this problem will be added if the marks obtained for the above 4 problems do not add upto 25. So, one can get upto 3 grace marks by doing this problem)*. Write a Prolog program for giving library users only basic facilities like referencing and enquiries if he/she has an overdue book. Otherwise, a user is allowed referencing, enquiries, borrowing and inter-library-loans. (Hint: Use `cut' to implement if-then-else. The program is less graceful :-).