NATIONAL UNIVERSITY OF SINGAPORE

November 1999 Time Allowed: 2 Hours

1. This examination paper consists of FIVE (5) questions and comprises TWELVE (12) printed pages including the cover page.
2. Write your answers in the blank spaces in this answer book only. Write on one side only.
3. This is an OPEN BOOK examination.
4. Please fill in your Matriculation Number below. Also write your matriculation number on the top right hand corner of every page.

Matriculation Number:

(a)  Is h’(n) admissible? Why?(4%)

(b)  Is h’(n) more informed than h(n)? Why?(3%)

(c)  Is h’(n) monotonic? Why?(3%)

(d) Using f(n) = g(n) + h’(n), where g(n) is the number of moves from the start state, draw a search tree from start to goal based on the best first search. In each node of your search tree, draw the board configuration and indicate the value of f(n), g(n) and h’(n) for the configuration. (The start and goal states are reproduced here for your easy reference) (10%)

 

 

2. A Re-write Production Rule System maintains a rule base containing 10 context free grammar rules as follows:

(a) Show the operation of the production system by completing the following table until no more rules can be fired (i.e. when the conflict set is empty.)(10%)

2.(b) Draw the space searched by the above execution of rules, indicating the direction of search. (7%)

(c) The search space constructed in 2(b) is actually a parse tree. Is this parse tree a top-down parse tree or a bottom-up parse tree? Explain your answer. (3%)

3. (a) Evaluate the following s-expressions:(6%)

 

(append ’(a b) ’(c d) ’(e f))
Þ

(append ’((a b) (c d)) ’(e f))
Þ

(length ’((a b) (c d) (e f)))
Þ

length ’(((a b) (c d)) (e f)))
Þ

(reverse ’((a b) (c d) (e f)))
Þ

(reverse ’(((a b) (c d)) (e f)))
Þ

(b) Define your own "reverse" function, named "my-reverse" that gives the same output as the system function "reverse". Your "my-reverse" function must be recursive. (8%)

 

 

(c) A palindrome is a list that has the same sequence of elements whether it is read from left to right or from right to left. A function "palindromize" is to take an input list and returns a parlindrome that is twice as long. Thus

(parlindromize ’(a b c d e f))
Þ (a b c d e f f e d c b a)

Define parlindromize using "append" and "my-reverse". Your function definition need not be recursive but "append" and "my-reverse" must be used. (4%)

 

(d) What will be the output of (parlindromize ’((a b) (c d) (e f))) ? (2%)

4. The following set of predicate calculus expressions is modified from the text book:

1. collie(fred)
2. master(fred, sam)
3. day(saturday)
4. warm(saturday)
5. trained(fred)
6. " X [spaniel(X) Ú (collie(X) Ù (trained(X)) Þ gooddog(X)]
7. " (X,Y,Z) [gooddog(X) Ù master(X,Y) Ù location(Y,Z) Þ location(X,Z)]
8. day(saturday) Ù warm(saturday) Þ location(sam,park)
9. day(saturday) Ù Ø (warm(saturday)) Þ location(sam,museum)

(a) Transform the above expressions into conjunctive normal form. (10%)

(b) Show that Fred is a good dog by resolution refutation using set-of-support strategy. (5%)

(c) Use answer extraction process of resolution refutation to answer the following question: Where is Sam? (5%)

5. (a) Why are there two possible sets of labeling as shown below resulted from the Constraint Propagation/Satisfaction Algorithm? Give your interpretation next to the respective diagrams. (5%)

                    (i)

(b) Assume that the following diagram has been labelled partially in the middle of execution of Constraint Propagation/Satisfaction Algorithm, leaving only 7 vertices to be further labelled, in the order of A, B, C, D, E, F, G in each cycle.

Using the information of the present state of partial labeling, continue to label these 7 vertices in the order of A, B, C, D, E, F, G until the algorithm halts. To do so, fill in the following table. The labeling should complete in 2 or 3 cycles. (10%)

5.(c) Do you get a unique set of labeling or do you get more than one set of labeling? Show your answer by labeling the following diagrams. (3 diagrams are reproduced for your use but you need not use them all). Interpret your labeling next to the respective drawings. (5%)