ASSIGNMENT 1. Due November 28.
=============================

Total points: 40
-----------------

1. (5 points) 

Translate the following sentences into logic formulas:

     (a) Everybody who drives a car has a driving license.
     (b) Thom does not drive.
     (c) If John and Peter love Mary then neither Peter nor Mary loves John.
     (d) All students except John attended the lecture.
     (e) Nobody can solve every problem. 
     (f) Somebody knocked at the door.

     Assuming that (a) and (b) are asserted, can you conclude that
   
     (g) Thom does not have a driving license.
     (h) Nobody drives a car without a driving license.
    
================================================================================

2.  3 Points.
  
    Write the following terms in the corresponding tree form. For lists,
    use the dot (.) as the functor and [] for the empty list:

    (a) [a|[f(b),c]]
    (b) [a|b]
    (c) [f(a,a),b|[]]
    (d) f([a,[b,c],d]) 
    (e) [[]|[[]]]

================================================================================

3.  4 points.

    Write a binary predicate factorial(N,F) that succeeds iff F = N!.  
    Write two versions of this predicate: with and without an accumulator,
    and compare their behavior on big inputs (1000000 and above, for instance).
    What difference do you notice?
  
================================================================================

4.  5 points.

    Write a predicate zip_and_append(L1,L2,L3,L4), which succeeds if
    the list L4 is obtained by zipping the lists L1 and L2 together
    and appending to its result the list L3.

    Use difference lists, not the 'append' predicate. 

    Sample runs:

    ?- zip_and_append([1,2,3], [a,b,c], [], L).
    L = [[1, a], [2, b], [3, c]].

    ?- zip_and_append([1,2,3], [a,b,c], [f(a),f(b)], L).
    L = [[1, a], [2, b], [3, c], f(a), f(b)].

    ?- zip_and_append([1,2,3], [a,b,c], L, [[1,a],[2,b],[3,c],f(a),f(b)]).
    L = [f(a), f(b)].

    ?- zip_and_append([],[],[f(a),f(b)], L).
    L = [f(a), f(b)].

    ?- zip_and_append([1,2,3,4],[a,b,c],[f(a),f(b)], L).
    false.


================================================================================

5.  4 points.
  
    Take the goal zip_and_append([1,2],[a,b],[f(a),f(b),f(c)],L) and draw
    a complete derivation tree for the program that solves the previous
    problem. Indicate substitutions, place markers, backtracking (if any),
    and the result.

================================================================================

6.  4 points.

    Define the predicate palindrome(Word) that recognizes palindromes.
    A word is a palindrome if it reads the same in the forward and in
    the backward directions. For example:

    ?- palindrome(madam).
    true.

    ?- palindrome(sir).
    false.

================================================================================

7.  4 points.
  
    The program below implements the definition of alternating factorial:

    alternating_factorial(1) = 1.
    alternating_factorial(n) = n! - altermating_factorial(n-1).

    However, the programming style is bad. Read Coding Guidelines for Prolog 
    (http://arxiv.org/pdf/0911.2899) and, following them, reformat the program
    and add comments.
  
alternatingFactorial(N1, N2) :- N1>1, factorial(N1,FN ),N11 is N1-1,
                      alternatingFactorial( N11, F1),N2 is FN -F1.

alternatingFactorial(N,1):- N=1.

================================================================================

8. 5 points.

   Implement the predicate alternating_factorial_acc that redefines
   the alternating factorial predicate with the help of an accumulator,
   making sure that the recursive call is the last subgoal in the
   recursive clause (unlike in the program in problem 7).

   Sample runs:

   ?- alternating_factorial_acc(1, F).
   F = 1 ;
   false.

   ?- alternating_factorial_acc(2, F).
   F = 1 ;
   false.

   ?- alternating_factorial_acc(3, F).
   F = 5 ;
   false.

   ?- alternating_factorial_acc(4, F).
   F = 19 ;
   false.

   ?- alternating_factorial_acc(5, F).
   F = 101 ;
   false.

   ?- alternating_factorial_acc(6, F).
   F = 619 ;
   false.
   
================================================================================

9. 4 points.

   Implement the predicate shift(List, N, Shifted_list), which succeeds if 
   Shifted_list is obtained from List by shifting it left in N elements.

   Sample runs:
  
   ?- shift([1,2,3,4,5,6,7,8,9,10], 0, L).
   L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] ;
   false.

   ?- shift([1,2,3,4,5,6,7,8,9,10], 1, L).
   L = [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] ;
   false.

   ?- shift([1,2,3,4,5,6,7,8,9,10], 2, L).
   L = [3, 4, 5, 6, 7, 8, 9, 10, 1, 2] ;
   false.

   ?- shift([1,2,3,4,5,6,7,8,9,10], 5, L).
   L = [6, 7, 8, 9, 10, 1, 2, 3, 4, 5] ;
   false.

   ?- shift([1,2,3,4,5,6,7,8,9,10], 9, L).
   L = [10, 1, 2, 3, 4, 5, 6, 7, 8, 9] ;
   false.

   ?- shift([1,2,3,4,5,6,7,8,9,10], 10, L).
   L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] ;
   false.

   ?- shift([1,2,3,4,5,6,7,8,9,10], 96, L).
   L = [7, 8, 9, 10, 1, 2, 3, 4, 5, 6] ;
   false.

   ?- shift([1,2,3,4,5,6,7,8,9,10], -1, L).
   L = [10, 1, 2, 3, 4, 5, 6, 7, 8, 9] ;
   false.
   
================================================================================

10. (2 points) 

   What does Prolog return to the following queries?
   (1)   [a,X] = [a,b,c,d].
   (2)   [a,X] = [a,[b,c,d]].
   (3)   [a|T] = [a,b,c,d].
   (4)   [a|T] = [a,[b,c,d]].
   (5)   [_,_,X|T] = [a,b,c,d,e].
   (6)   X = 2+2.
   (7)   X is 2+2.
   (8)   1+3 = 2+2.
   (9)   1+3 =:= 2+2.
  (10)   1+3 =< 2+2.
  (11)   2 >= 10 mod 4.
  (12)   f(X) >@ f(a).
  (13)   f(a) @=< f(a,a).
  (14)   a @> X.
  (15)   a @> f(a).
  (16)   a(a) @> f(a).
  (17)   a(a,a) @> f(a).
  (18)   2 > 3+5.
  (19)   X is Y + 3.
  (20)   Y = 5, X is Y + 3.

================================================================================