CSE341 -- Assignments -- CLP(R)

Due 1 June 2000

Submission directions: Please turn in both printed and electronic copies of your code. The print submission is due in quiz section on the due date above (or later that day). You may e-mail the electronic copies to Keunwoo (klee@cs) anytime the same day. For full credit, you must follow the submission guidelines.

1. Don't hand in the answer to this question.

   Define the append and sum relations as follows:

      append([],L,L).
      append([H|T],L,[H|U]) :- append(T,L,U).
   
      sum([],0).
      sum([X|Xs],X+S) :- sum(Xs,S).
   

   Try append on the following. In each case reject the answers to see what happens when CLP(R) backtracks.

      append([a,b,c],[w,x,y,z],L).
      append([a,b],Y,[a,b,c,d]).
      append([a,c],Y,[a,b,c,d]).
      append(X,Y,[a,b,c,d]).
      append(X,Y,Z).
   

   Now try sum on the following, again backtracking when possible.

      sum([5,10,20],N).
      sum([5,10,20],8).
      sum([5,X],100).
      sum([5,X,Y],100).
      sum(A,100).
   

2. Don't hand in the answer to this question. Exercise P4.3 from Marriott and Stuckey (define the abs predicate). Try your predicate working with various combinations of constants and variables as arguments, including both arguments constants, both variables, and one constant and one variable. Backtrack to find multiple answers. Also draw the derivation tree for abs(N,10).

3. Draw part of the derivation tree for sum(A,S) (so that your tree includes at least two different answers).

4. Define a predicate average that finds the average of a list of numbers. Decide what the correct way is to handle the average of an empty list of numbers, and justify your answer in a comment. Show your predicate working with various combinations of constants and variables as arguments, including both arguments constants, both variables, and one constant and one variable. Backtrack to find multiple answers.

5. Write a rule coins to find all the combinations of U.S. coins, except for pennies, whose value is a given amount. (I'm leaving out pennies since otherwise there are too many combinations. Include 50 cent and 1 dollar coins though.) For example:

   coins(10,L)
   

   should succeed with L=[10], i.e. one way of getting 10 cents is a single dime. On backtracking it should also succeed with L=[5,5], i.e. two nickels.

   It's OK to return the same answer a second time when you backtrack -- for example, if you are finding combinations for 15 cents, you can return [10,5] and also [5,10].

   Using your coins rule:

   1. Find all the combinations of coins with value 35 cents.
   2. Find all the combinations of coins with value 12 cents. (Remember, no pennies.)
   3. Find the value of two quarters and a dime.
   4. Find all the amounts of money that can be given using exactly two coins.
   5. Find all the amounts of money that can be given using 0 to 2 coins.