COT 3541 Section U01 Spring 2017 Optional Assignment =================== Due: Wednesday, April 26th, 2017 Do the problem that is next to your name. Do not use bagof, setof, findall. Mail me the assignment, either as a text file or pasted directly in the body of the e-mail. Indent the continuation lines, put comments, avoid wrap around lines and include your name in the header comment. Below is a description of the predicates and tests. 1. is_multi(M) is satisfied if every element of M has the form X/N, where X is an atom and N is an integer greater than 0. Moreover, M does not contain two elements with the same atom. For example, is_multi([]), is_multi([a/2, b/2]) are satisfied, but is_multi([a,b/2]), is_multi([a/0, b/2]), is_multi([a/2,2/4]), is_multi([a/2,b/3,a/2]), is_multi([a/3, b/-4,c/1]) are not. Test the goals listed in the example. 2. form_multi(Set, Multi_set) takes as input a list of atoms and outputs a multiset with elements X/N, where X is an element of Set and N is the number of occurrences of X in Set. For example, form_multi([a,b,a,b,c,a,c,d],M) is satisfied with M=[a/3,b/2,c/2,d/1] because a occurs 3 times, b and c twice and d once. Test the goals form_multi([a,b,a,a,a,c,a,b,d,c,c,a],M), form_multi([],M), form_multi([a,b,b,b,b,b,a,c,a,b],M). 3. multi_lub(M1,M2,M) is satisfied if M is the least upper bound of the multisets M1 and M2. The members of M are pairs X/N, where X is an atom that occurs in at least one of the sets M1 and M2 and N is the largest of the the indices of X in M1 and M2. It X does not occur in one set then its index in that set is 0. So, multi_lub([a/2,b/3,c/2],[b/3,c/4,d/1],M) is satisfied if M=[a/2,b/3,c/4,d/1]. The index of a in M is the largest of 2 and 0, the index of b is the largest of 3 and 3, the index of c is the largest of 2 and 4, and the index of d is the largest of 0 and 1. Test the goals multi_lub([],[a/3,b/3],M), multi_lub([a/2,b/2,c/1],[c/2,b/1,d/2],M), multi_lub([a/2,b/1],[],M), multi_lub([a/3,b/4,c/2],[d/4,c/2,a/4],M). 4. multi_glb(M1,M2,M) is satisfied if M is the greatest lower bound of M1 and M2. This means that the members of M are the pairs X/N where X occurs in BOTH M1 and M2, and N is the smaller of the two indices. For example, multi_lub([a/3,b/2,c/5],[a/2,c/7,d/3],M) is satisfied with M=[a/2,c/5] because 2 is the smallest of 3 and 2, and 5 is the smallest of 5 and 7. The atoms b and d do not occur in M because they do not occur in both multisets. By the same reason multi_glb([a/3,b/5],[c/5,d/6],M) produces M=[]. Test the goals multi_glb([a/2,b/3],[b/2,d/4],M), multi_glb([],[a/2,b/3,c/1],M), multi_glb([a/4,b/2,c/1],[],M), multi_glb([a/2,b/3],[d/1,c/6],M). 5. multi_subset(M1,M2) is satisfied if every atom of M1 occurs in M2 with an index at least as big. For example, multi_subset([a/3,b/2],[a/5,b/2,c/5]) is satisfied because the indices of a and b in the second set are at least as big as their indices in the first set. At the same time, multi_subset([a/2,b/3],[a/4,b/1, c/4]) fails because the index of b in the first set is bigger than the index of b in the second set. Test the goals multi_subset([a/2,b/3],[b/1, a/4, c/4]), multi_subset([a/3,b/2],[a/5,b/2,c/5]), multi_subset([a/2,b/3], [b/3,a/2]), multi_subset([],[]), multi_subset([a/2,b/1],[]). 6. list_index(X,List,N) is satisfied if the Nth item of List is X. Test the goals, list_index(X,[a,b,c],4), list_index(c,[a,c,b],N), list_index(a,[b,c,d],N), list_index(X,[],N). Keep in mind that the index of the first item in a list is 1, not 0. So, list_index(a,[a,b],N) must return N = 1. 7. subsequence(List1, List2) is satisfied if the elements of List1 occur in the same order in List2. That means that whenever X precedes Y in List1 X occurs before Y in List2. For example subsequence([a,b,c], [1,a,2,3,b,4,5,c,6]) is satisfied because in the second list a occurs before b and b occurs before c. The first list may have duplications, so subsequence([a,b,a,c],[a,1,c,2,a,b,3,4,b,4,c,5,6,a,7,c]) is satisfied, because the first a, the first b, the third a, and the third a have the same order in second list as in the first. Test the goals subsequence([a,b,c], [1,2,3,c,a,4,5,b]), subsequence([a,b,a],[b, 1,2,a,4,5,a]), 8. We recall that the built in predicate T =.. L is satisfied if T is a term and L is the list that contains the functor and the main subterms of L. For example, f(a,g(b)) =.. L is satisfied when L = [ f, a, g(b) ], and a =.. List is satisfied when List = [a]. Use =.. to define the predicate subterm(T1,T2) which is satisfied when T1 is a subterm of T2. You may assume that T1 and T2 have no variables. You may also want to use the built in predicates atomic(X) or compound(X) that check if X is an atomic term and a structure, in this order. 9. Write a prolog predicate intersect(List1, List2, List) that is satisfied when List contains all items that occur in both List1 and List2. You may assume that List1 and List2 have no duplicate items. For example intersect([1,3,5,7], [1,2,5,6,8],L) is satisfied if L=[1,5]. 10. Implement the merge sort method for a list of integers. So, write the predicate mergeSort(List, SortedList) is satisfied if SortedList is List sorted in increasing order. You must write the predicates mergeSort, split(List, List1, List2), and merge(SortedList1, SortedList2, SortedList). The predicate split splits List into 2 halves, List1 and List2. The predicate merge merges the sorted lists SortedList1 and SortedList2 onto SortedList. 11. add_multi(M1, M2, Sum) is satisfied if Sum is the sum of the multisets M1 and M2. This means that the members of Sum are the pairs X/N where N is the sum of the indices of X in M1 and M2. If X does not occur in one of them, then the index is 0. For example, add_multi([a/2,b/3,c/4],[a/1,c/2,d/3],M) is satisfied if M=[a/3,b/3,c/6,d/3]. Test the goals, add_multi([a/2,b/2,c/3],[d/4,b/3,a/2],M), add_multi([],[a/2,b/1],M), add_multi([a/2, b/3],[],M), add_multi([a/2,b/1,c/4],[d/2],M). 12. We represent a chess board square by Row/Col, where Row and Col are integers from 1 to 8. A queen moves on a row, a column or on the diagonal. Write the predicate queen_move(R1/C1, R2/C2) which is satisfied if the queen can move from R1/C1 to R2/C2 in a single move. Use =\= for not equal. 13. We represent a chess board square by Row/Col, where Row and Col are integers from 1 to 8. A knight moves in the shape of L. For example, if the knight is on 2/3 it can move to 1/1, 1/5, 3/1, 3/5, 5/2, 5/4. The other 2 squares that satisfy the L move are -1/2 and -1/4, but those are off the board. Write the predicate knight_move(R1/C1, R2/C2) which is satisfied if the knight can move from R1/C1 to R2/C2 in a single move. 14. Assume that you have the predicates parent(X,Y) % X is a parent of Y male(X) % X is a male female(X) % X is a female define the predicates mother(X,Y) % X is the mother of Y ancestor(X,Y), % X is an ancestor of Y half_brother(X,Y) % X is a half brother of Y sister(X,Y) % X is a (full) sister of Y X is not an ancestor X, but his/her parents, grandparents, greatgrandparents, ... are. Use =\= for not equal. 15. Assume that you have the predicates parent(X,Y) % X is a parent of Y male(X) % X is a male female(X) % X is a female define the predicates father(X,Y) % X is the father of Y descendent(X,Y), % X is an ancestor of Y sibling(X,Y) % X is a (full) sibling of Y grandfather(X,Y) % X is a grandfather of Y X is not an descendent of X, but his/her children, grandchildren, greatgrandchildren, ... are. X is not a sibling of X. Use =\= for not equal. 16. Implement the selection sort in prolog for a list of integers. You must write the predicate sort(List, SortedList) that is satisfied if SortedList is list sorted in increasing order. You may want to write the predicates minItem(X,List) that is satisfied if X is the smallest Item in List deleteItem(X,List,RList) that is satisfied if Rlist is obtained by deleting the first occurrence of X from List. 17. Do the knight's tour on a N by N chess board. Represent the squares as pairs Row/Col, where 1 <= Row, Col <= N. The knight must traverse all NXN squares of the board without lending in the same square twice. The start command is knightTour(StartSq, N, Solution) where StartSq is the initial position, and Solution is the list of all squares traversed by the knight. Recall that the knight moves in the shape of L. For example if N=5 and the knight is on 2/3 it can go to 1/1, 1/5, 3/1, 4/2, 4/4, 3/5. 18. Implement the quickSort method in Prolog, i.e. write the predicate quickSort(List, SortedList) where list is a list of integers and SortedList is the list sorted in increasing order. You must also write the predicate partition(List, Pivot, Small, Big) that splits List into the two arrays Small and Big. Take the first item of list as the pivot. 19. Write the prolog predicate subSum(List, Sum, Sublist) where List is a list of integers, Sum is an integer and Sublist is a sublist of List whose sum is equal to Sum. For example, subSum([1,2,3,4], 8, Sublist) is satisfied if Sublist = [1, 3, 4]. Here are the problem numbers for each student. Problem Assignment: =================== Name Problem ---- ------- 1. Roicxy Alonso #1 2. Trent Alonzo #3 3. Daniel Alvarez #4 4. Giuliana Avogadro #5 5. Masood Bolooki #6 6. Ian Cuvalay #7 7. Justin Danglade #8 8. Nicolas Gonzalez #9 9. Moise Jerome #10 10. Alexander Mohamed #11 11. Obiajulu Nwankwo #12 12. Edward Phillips #13 13. Kyle Pulido #14 14. Rogelio Robedo #15 15. Adreina Rojas #16 16. Abraham Saiovici #17 17. Juan Valladares #18