Please make sure that your source code can be compiled and executed under SWI Prolog on Unix. For a brief explanation on how to run SWI Prolog and how to load and execute programs, see http://www.cse.psu.edu/~catuscia/teaching/prolog/index.html

1. [Points 20] Assume given a set of facts of the form father(name1,name2) (name1 is the father of name2).
   1. Define a predicate brother(X,Y) which holds if X and Y are brothers.
   2. Define the predicate uncle(X,Y) which holds if X is an uncle of Y, namely X is a brother of the father of Y.
   3. Define a predicate cousin(X,Y) which holds iff X and Y are cousins.
   4. Define a predicate grandson(X,Y) which holds iff X is a grandson of Y.
   5. Define a predicate descendant(X,Y) which holds iff X is a descendant of Y.
   Do not worry about the order of the answers, about repetitions of the same answer and about answers that represent symmetric solutions. However, avoid infinite loops and avoid wrong answers.

   You may find useful to use the relation not(X=Y), which holds if and only if X and Y are instantiated to different values.

2. [Points 15] A directed graph can be represented in Prolog by listing the arcs among the nodes, as a set of facts. For instance, the clause

      arc(a,b).
   

   would represent the existence of an arc going from the node a to the node b.

   Define in Prolog a predicate path(X,Y) which holds iff there is an path from the node X to the node Y. For simplicity, assume that the graph does not contain cycles.

Example: Assume that we have the following graph:

   arc(a,b).
   arc(a,c).
   arc(b,c).
   arc(b,d).
   arc(c,e).

We should get the follwowing answers:

   ?- path(a,a).
 
   Yes

   ?- path(a,e).

   Yes

   ?- path(d,e).

   No

3. [Points 20] Define the predicate

      sublist(L1,L2)
   

   representing the relation "L1 is a sublist of L2", i.e. "L1 contains a sequence of contiguous elements identical to L2".

   Example:

      ?- sublist(L,[1,2,3]).
    
      L = [] ;
    
      L = [1] ;
    
      L = [1, 2] ;
    
      L = [1, 2, 3] ;
    
      L = [] ;
    
      L = [2] ;
    
      L = [2, 3] ;
    
      L = [] ;
    
      L = [3] ;
    
      L = [] ;
    
      No
   

   Again, don't worry about repetitions of the same answer and about the order of the answers. Avoid infinite loops, at least for queries where the second argument is completely instantiated (i.e. it does not contain variables).

4. [Points 25] Define the predicate

      flat(L1,L2)
   

   representing the relation "L2 is the flattened version of L1". In other words, L1 is a list whose elements can be lists, whose elements can be lists again, etc. L2 should contain the same items of L1, and in the same order, but where all levels of square brackets (eccept the top one) are "stripped off". Note:You are not allowed to use the predefined predicate flatten.

   Example:

      ?- flat([],L).
    
      L = [] ;
    
      No
   
      ?- flat([1,2],L).
    
      L = [1, 2] ;
    
      No
   
      ?- flat([1,[[2],[[3]]],[],[4,5]],L).
    
      L = [1, 2, 3, 4, 5] ;
    
      No
   

   Avoid infinite loops, at least for queries where the first argument is completely instantiated (i.e. it does not contain variables).

   You might find useful to use a predicate not_list(X), which holds iff and only if X is not a list. Such predicate can be defined as

      not_list(X) :- not(X=[]), not(X=[_|_]).
   

   Note that the predicate flat as defined above could not be implemented in ML, because in ML lists are homogeneous, i.e. all the elements must be of the same type.

5. [Points 20] Define a predicate quicksort(L,K) which, given a list of integers L, returns an ordered list K obtained from L with the method of quicksort.

   Note: you can compare two integers, in Prolog, by using the infix predicate "<". Example:

      ?- 4 < 5.
   
      Yes
   
      ?- 5 < 4.
   
      No
   

   Your definition of quicksort should work when the first argument is instantiated. Example:

      ?- quicksort([5,4,8,1,6],K).
    
      K = [1,4,5,6,8] ;
    
      No