COMP4411, Fall 2022 Assignment Two
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.
2022-10-24