Computer Science 3675
Fall 2011
Practice Questions for Quiz 7

1. True or false.

   1. Using a cut can reduce the time used by a program. Answer

   2. Using a cut can reduce the amount of memory used by a program. Answer

   3. Using a cut in a predicate definition usually restricts the modes in which a predicate can run. Answer

   4. It is rare to find cuts in logic programs. Answer

2. Explain negation-as-failure. What is its goal, and how does it work?

   Answer

3. Does negation-as-failure always do correct logical negation?

   Answer

4. In a logic programming style, write axioms for computing predicate allsame(X), which is true just when all members of list X are the same. For example, allsame([5,5,5]) is true, as is allsame([a,a]), but allsame([2,4,4]) is false. Note that allsame([]) is true, and allsame([b]) is true.

   Answer

5. In a logic programming style, write axioms for computing predicate samelength(X,Y), which is true just when X and Y are lists that have the same length.

   Answer

6. Two individuals are cousins if they have a grandparent in common, but they are not the same person, and are not siblings. Using predicate grandparent(X, Y), meaning that X is a grandparent of Y, and predicate sibling(X, Y) meaning that X and Y are siblings, write a definition of cousin(X, Y) using Prolog notation, meaning that X and Y are cousins.

   Answer

7. The append predicate is defined as follows in Prolog.

     append([], Y, Y).
     append([A|X], Y, [A|Z]) :- append(X, Y, Z).
   

   You would like to define a predicate double(X), which is true if list X has the form Y ++ Y, for some Y. For example, double([a,b,c,a,b,c]) is true, but double([a,b,c,a]) is false.

   Which of the following is a correct definition of double in Prolog?

   1. double(X) :- append(X,X,Y).
   2. double(X) :- append(Y,Y,X).
   3. double(X) :- append(X,Y,X).
   4. double(X) :- append(Y,X,X).

   Answer

8. You would like to write a definition of predicate member, where member(X, L) is true if X is a member of list L. Which of the following is a correct definition of member?

   1. member(X, L) :- append(A, [X|B], L).
   2. member(X, L) :- append(X, Y, L).
   3. member(X, L) :- append(L, [X|Z], Y).
   4. member(X, L) :- append([X|L], Y, L).

   Answer