Programming Languages Homework 6 Due 11/5

Implement the following prolog relations. If applicable, the relation should be able to respond to the backward query. You may use built-in predicates append, member, not, reverse, and length.
(15 points) Define the predicate compute-change(Money,Quarter,Dime,Nickle,Penny). You may assume that Money is less than 100 (cents) and you want to minimize the number of coins you should give. (No backward query)
- compute-change(33,Q,D,N,P).
```
Q = 1 D = 0 N = 1 P = 3
```
(15 points) Define the predicate compose(L1,L2,L3) such that L3 consists of the element of L1 precedes that of L2 in order until one of them becomes nil and then append that non-nil list at the end.
- compose([a,b,c],[x,y,z],L).
```
L = [a,x,b,y,c,z]
```
- compose([a,b,c],[x,y],L).
```
L = [a,x,b,y,c]
```
- compose(L1,L2,[a,b,c]).
```
L1 = [] L2 = [a,b,c] ;
L1 = [a] L2 = [b,c] ;
L1 = [a,c] L2 = [b];
L1 = [a,b,c] L2 = []
```
(15 points) Define the predicate palindrome(Base,Result). You may assume that Result is always even length list. However, you must show that your answer is the only possible answer.
- palindrome([m,a,d],R).
```
R = [m,a,d,d,a,m] ;
no
```
- palindrome(B,[n,i,s,s,i,n]).
```
B = [n,i,s] ;
no
```
(15 points) Klefstad is hosting a party of an international organization. Not everybody speaks the same language and some of them speak more than 1 language. He invited 10 guests and including himself he plans to have a ROUND TABLE CHATTING SESSION. To make everybody comfortable, he sets the following rules. . Each person must be able to have a conversation with both people they are seated next to (in some language).
- No two females sit next to each other.
- Information about the invitee and the host is as following:
  - Klefstad,Chris,Emily,Heidi, and Isacc speaks in English.
  - Beth,Gong, and Isacc can speak in French.
  - Chris,Dongjoon,Fred, and Jane can speak in Korean
  - Gong,Heidi,Jane and Kenny can speak in Chinese
  - Beth,Emily,Heidi,Chris, and Jane are females.
- Find all possible seat arrangment starting with Klefstad. There are less than 5 unique solutions. HINT: Try on much simpler set of databases and debug your program using trace. Since there are 10! possible arrangements w/o any constraints, it may take time. For any case, you may assume that there are at least 3 people in the party.
- Note there is a solution for this problem on the web, but you can't use it or anything like it. If you get stumped, you can take a look at Prolog solution.
At a baseball game, five men, L, M, N, O, and P and five women, S, T, U, V, and W, occupy a row of ten seats. The men are in odd numbered seats, starting from the left; each woman sits to the right of the man she is dating. O is V's date. W is not at the right end of the row and the man she is dating is not at the left end of the row. N is one seat from the right end of the row. The man dating W likes T best among the other women and insistes on being seated to the right of T. M and his date occupy the middle pair of seats. V sits next to M. Ask and answer each of the following questions:
- (5 points) What are all the valid seating arrangement from left to right?
- (5 points) Who may U's date be?
- (5 points) Who occupies the seat furthest to the left?
- (5 points) Who occupies the seat furthest to the right?
- (5 points) Which other women are nearest T?
- (5 points) What is the position of T?
- (10 points) Wich of the following could be determined exactly if the position of either L or P were given?
  - The identity of L's date.
  - The identity of P's date.
  - The identity of L's date or of P's date but not both.
  - Which woman is not seated between two men.
  - Who is sitting to O's left.
Note if you are using Unix for the first time, check out my introduction to Unix at Unix Introduction
Submit: a listing of all your prolog programs and sample runs demonstrating that they work correctly. You may use the sample inputs I gave, but you should add some more to help convince us that your relationships are correct. Also submit electronic verions of all your relations so we may run them if necessary.