CSE 505 - Autumn 2001 - Assignment 3

1. Write rules defining a predicate scale(N,L1,L2) that takes a number N, and lists of numbers L1 and L2. Each element of L2 should be N times the corresponding element of L1. For example, scale(10,[1,2,3],K) should succeed with K=[10,20,30]; scale(A,[1,2,3],[2,4,6]) should succeed with A=2; and scale(5,[1,A],[B,10]) should succeed with B=5,A=2.

2. Write rules defining a sublist(S,L) predicate that succeeds if S is a sublist of L. For example, sublist([3,4,5],[1,2,3,4,5,6]) should succeed. The goal sublist(A,[1,2,3]) should find all of the sublists of [1,2,3] on backtracking (A=[], A=[1], A=[1,2], A=[1,2,3], A=[2], A=[2,3], A=[3]). It's OK if your rules return the same answer more than once (just not infinitely often!).

3. 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.

4. Marriott and Stuckey, Problem P6.12 (page 210).

5. Marriott and Stuckey, Problem P6.13 (page 210).