Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP4411, Fall 2022 Assignment Two

Note:  To show their correctness,  your submission should  in- clude test-cases, aside from your defined Prolog procedures.

1.  (15 marks) Define the following predicates:

(a) member(X,L), which holds iff element X occurs in list L. (b)  subset(L,K), which holds iff list L is a sublist of list K.

(c)  disjointLists(L,K), which holds iff the lists L and K do not have any element in common.

2.  (40 marks) Define the following predicates:

(a)  occursNTimes(X,L,N), which holds iff the element X occurs N

times in the list L.

(b)  occursOnNthPosition(L,N,X), which holds iff X is the element

occurring in position N of the list L (The first position of the list is position 1).

(c)  listSum(IntL,Sum) which, given a list of integers IntL, returns the sum Sum of all the elements of IntL.

(d)  listAddedUp(IntL,  AddUpList) which, given a list of integers IntL, returns AddupList, a list of integers in which each element is the sum of all the elements in IntL up to the same position. Example: if IntL is [1, 2, 3, 4], AddUpList would be [1, 3, 6, 10].

3.  (15 marks) quicksortListIntoOrdered(List,Ordered) which, given a list of integers List, returns an ordered list Ordered obtained from   List.  The sorting algorithm implemented will have to be quicksort!   The pivot value will have to be the head element.   Quicksort pseu-   docode below:

QuickSort(S)  (S  is  the  list  to  sort)

1:  if  |S|  <=1  return  S

2:  select  pivot  p  in  S

3:  partition  elements  of  S  into:

L  =  elements  of  S  less  than  p

E  =  elements  of  S  equal  to  p

U  =  elements  of  S  greater  than  p

4:  return  QuickSort(L);  E;  QuickSort(U)

Standard  QuickSort:  we select the pivot by simply letting p be the first element in S . Example:

1) S = [15, 25, 12, 2, 37].

2) p = 15, L =[12, 2]; M =15; U =[25, 37]

3) p = 12, L=[2]; M=12; U=[];            p = 25, L=[]; M=[25]; U=[37];

4) 2, 12, 15, 25, 37.