ASSIGNMENT 1. Due November 23.
=============================

Total points: 40

Grading with respect to points P:
35 < P:        1 very good
29 < P =< 35:  2 good
23 < P =< 29:  3 satisfactory
19 < P =< 23:  4 adequate
P =< 19:       5 not adequate

--------------------------------------------------------------------------------

1. (5 points) 

Translate the following sentences into logic formulas:

     (a) Some successful soccer coaches were good soccer players.
     (b) Ernst Happel is the most successful Austrian soccer coach.
     (c) Neither Ibsen nor Proust were awarded the Nobel prize in literature,
         while Sartre declined it.
     (d) John solved all homework problems except the last one.
     (e) Nobody can solve every problem. 
     (f) If I am to go, I must pack at once, for I have only half an hour.

     Assuming that (a) and (b) are asserted, can you conclude that
   
     (g) Ernst Happel was a good soccer player.
     (h) Not all successful soccer coaches were good soccer players.
     
     
================================================================================

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,b,c,d]
    (b) [a|[b,c,d]]
    (c) [a,b,c,d,[]]
    (d) [a|[f(b),c]]
    (e) [a|b]
    (f) [f(a,a),b|[]]
    (g) f([a,[b,c],d]) 
    (h) [[]|[[]]]
    (i) f([a,f(b,c),d], e)
    
================================================================================

3.  (3 points)

    Write a binary predicate even_element(list, term) that succeeds if 
    'term' occurs in 'list' in an even position.

    Sample runs:
    ?- even_element([1], X).
    false.

    ?- even_element([1,2], X).
    X = 2 ;
    false.

    ?- even_element([1,2,3], X).
    X = 2 ;
    false.

    ?- even_element([1,2,3,4], X).
    X = 2 ;
    X = 4 ;
    false.

    ?- even_element([1,2,3,4], 2).
    true

    ?- even_element([1,2,3,4], 3).
    false.

    What does your program return of the following queries?
    ?- even_element(L, a).
    ?- even_element(L, X).


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

4. (4 points)

   Take your program that solves the problem 4 and draw the
   complete derivation tree (like those we did in the class)
   for the query even_element([1,2,3,4,5,6,7], X).
   
================================================================================

5. (4 points)

   Consider trees whose nodes may have at most 3 children. 
   The leaves of the tree are denoted by leaf(number), such as, 
   e.g., leaf(1), leaf(2), etc. 
   
   Define a predicate rearrange(tree1, tree2) that succeeds if 
   tree2 is a mirror image of tree1. 

   Sample runs:
   ?- rearrange(tree(leaf(1)), X).
   X = tree(leaf(1)) ;
   false.
   ?- rearrange(tree(leaf(1),leaf(2)), X).
   X = tree(leaf(2),leaf(1)) ;
   false.
   ?- rearrange(tree(leaf(1),leaf(2), leaf(3)), X).
   X = tree(leaf(3),leaf(2),leaf(1)) ;
   false.
   ?- rearrange(tree(tree(leaf(1),leaf(2)), leaf(3)), X).
   X = tree(leaf(3), tree(leaf(2),leaf(1))) ;
   false.
   ?- rearrange(tree(tree(leaf(1),leaf(2)), tree(leaf(3))), X).
   X = tree(tree(leaf(3)), tree(leaf(2),leaf(1))) ;
   false.
   ?- rearrange(X, tree(tree(leaf(3)), tree(leaf(2), leaf(1)))).
   X = tree(tree(leaf(1),leaf(2)), tree(leaf(3))) ;
   false.
   ?- rearrange(tree(tree(leaf(1),leaf(2)), tree(leaf(3),leaf(4))), X).
   X = tree(tree(leaf(4),leaf(3)), tree(leaf(2),leaf(1))) ;
   false.

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

6. (4 points)

   Write a predicate list_sum(list, sum) that succeeds of 'sum'
   is the sum of elements of 'list', consisting of numbers.

   Sample runs:

     ?- list_sum([1,2,3], 6).
     true.

     ?- list_sum([1,2,3], X).
     X=6.

     ?- list_sum([], X).
     X=0.

   What does your program do on the following queries?
     ?- list_sum(L, X).
     ?- list_sum(L, 2).
     ?- list_sum([a,b,c], X).
     
================================================================================

7.  (5 points)

    Fibonacci numbers, Lucas numbers and Fibonacci words are sequences 
    defined respectively as follows:

     fib(0) = 0
     fib(1) = 1
     fib(n) = fib(n-1) + fib(n-2), when n > 1.

     lucas(0) = 2
     lucas(1) = 1
     lucas(n) = lucas(n-1) + lucas(n-2), when n > 1.

     fib_word(0) = b
     fib_word(1) = a
     fib_word(n) = fib_word(n-1) fib_word(n-2),
                   concatenation of two words, when n > 1.

     Define a predicate sequence_element(name,n,el), which succeeds if 'el'
     is the 'n'-th element of 'name'-s sequence.

     Sample runs:

     ?- sequence_element(fib,5,X).
     X = 5 ;
     false.

     ?- sequence_element(fib,6,X).
     X = 8 ;
     false.

     ?- sequence_element(fib,10,X).
     X = 55 ;
     false.

     ?- sequence_element(fib,100,X).
     X = 354224848179261915075 ;
     false.

     ?- sequence_element(lucas,3,X).
     X = 4 ;
     false.

     ?- sequence_element(lucas,4,X).
     X = 7 ;

     ?- sequence_element(lucas,100,X).
     X = 792070839848372253127 ;
     false.
                                                
     ?- sequence_element(fib_word,3,X).
     X = aba ;
     false.

     ?- sequence_element(fib_word,4,X).
     X = baaba ;
     false.

     ?- sequence_element(fib_word,5,X).
     X = ababaaba ;
     false.

     ?- sequence_element(fib_word,6,X).
     X = baabaababaaba ;
     false.

     ?- sequence_element(fib_word,7,X).
     X = ababaababaabaababaaba ;
     false.

     ?- sequence_element(fib_word,10,X).
     X = baabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaaba ;
     false.

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

8. (3 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,b|X] = [a,b,c,d].
  (4)   [a,b|X] = [a,b,[c,d]].
  (5)   [X|Y] = [a|b].
  (6)   [X|Y] = [a,b].
  (7)   [X,Y] = [a|b].
  (8)   [X,Y] = [a,b].
  (9)   [_,_|_] = [a,b,c,d].
 (10)   [X,X|Y] = [a,b,c,d].
 (11)   [_] = [].
 (12)   [_] = [a].
 (13)   [_] = [a,b].
 (14)   [_|_] = [].
 (15)   [_|_] = [a].
 (16)   [_|_] = [a,b].
 (17)   X is 3+Y.
 (18)   X is 3+5.
 (19)   Y = 5, X is 3 + Y.
 (20)   X is f(3+5).
 (21)   2+3 > 6.
 (22)   f(2+3) > f(6).
 (23)   f(2+3) @> f(6).
 (24)   f(a,b) @< f(b,c).
 (25)   f(f(a)) @> f(g(b)).
 (24)   1+3 = 2+2.
 (27)   1+3 =:= 2+2.
 (28)   1+3 =< 2+2.
 (29)   2 >= 10 mod 4.
 (30)   3+4 @=< 7.
 
 
================================================================================

9. (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 carefully, 
   reformat the program, change variable names to more meaningful ones, 
   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.

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

10. (5 points)

  The letters e, t, and a are three most frequently appearing ones in 
  English texts. 
  
  Write a predicate frequencies(text, e_percentage, t_percentage, a_persentage) 
  that succeeds if e_percentage, t_percentage, and a_persentage represent 
  in percents the frequencies of occurrences of e, t, and a, respectively, 
  in the given text. Both upper and lower case appearances of these letters 
  count.

  Sample runs:
  ?- frequencies("This seems to be a difficult exercise.", E, T, A).
  E = 15.7895,
  T = 7.89474,
  A = 2.63158 ;
  false.

  ?- frequencies("How are strings represented in Prolog?", E, T, A).
  E = 13.1579,
  T = 5.26316,
  A = 2.63158 ;
  false.

  ?- frequencies("How can I avoid computing more than one answer?", E, T, A).
  E = 6.38298,
  T = 4.25532,
  A = 8.51064 ;
  false.