CSE 428: Quizzes

Spring 2001, CSE 428: Quiz 11.2 - 19 April 2001

Please write your Name and Student ID at the top of the page. By default, this quiz will be returned in Section 2 (morning section).

[Pts 2] Consider the following alternative programs to compute the reverse of a list:
```
   P1: rev([],[]).       
       rev([X|L],M) :- rev(L,K), append(K,[X],M).
          /* append is the builtin for lists concatenation */
```
and
```
   P2: rev(L,M) :- aux(L,M,[]).
       aux([],Acc,Acc).       
       aux([X|L],M,Acc) :- aux(L,M,[X|Acc]).
```
In what sense is the second program preferable to the fist? (only one answer, please)
- The second program is more flexible: it can be used "in reverse mode"
- The second program is more efficient: it is linear instead of quadratic
- The second program is more modular: it can be used in combination with difference lists
- The second program is more expressive: it can be used to compute the reverse of any kind of data structure
[Pts 2] Consider the standard way of representing trees in logic programming, and the following definition of a predicate p:
```
   p(leaf(X),1).
   p(node(T1,X,T2),N) :- p(T1,N1), 
                         p(T2,N2), 
                         N is N1 + N2. 
```
Consider now the query ?-p(t,N). where t is a term representing a certain tree. What is the result returned by it? (only one answer, please)
- N is the height of t
- N is the number of all the nodes in t
- N is the number of all the internal nodes of t
- N is the number of all the nodes on the frontier of t
[Pts 2] Consider the Prolog query ?- X is 1+2, Y = X+3. What is the result returned by it? (only one answer, please)
- error
- X = 3 Y = 6
- X = 3 Y = 3+3
- X = 1+2 Y = 1+2+3
[Pts 2] Consider the Prolog query ?- X = 3, not(X=2). What is the result returned by it? (only one answer, please)
- no
- yes
- error
- X = 3; no
[Pts 2] Assume given the following Prolog program:
```
 
   nat(0).
   nat(N) :- nat(M), N is M+1.
```
Consider now the query ?- nat(N). What is the result returned by this query? (only one answer, please)
- no
- yes
- N = 0; and then the computation enters an infinite loop
- N = 0; N = 1; N = 2; N = 3; ... (infinitely many answers)