CSCE 625
Homework Assignment #8
due: Tues, 11/24/09

1. Write a prolog function to remove duplicates from a list:

  ?- remdups([1,3,4,2,4,3,6,8,6,5,4,2,3,4,9],X).
  X = [1, 8, 6, 5, 2, 3, 4, 9] 


2. Implement prime factorization in Prolog.  Here is an example:

  ?- factor(120,M).
  M = [5, 3, 2, 2, 2] 
  ?- factor(7,P).
  P = [7] 

Note: you can use a simple algorithm that iterates from 1 up to N
or sqrt(N) and tests for divisibility using mod.  for example:

  divisible(N,X) :- M is N mod X,M=0.

You will probably want to write and call an auxilliary function that
builds up a list of factors as you go.


3. Write a logic program to compute the zeros of sin(x), that is the
values of x such that sin(x)=0, using Newton's method.

Newton's method says that, given a function f(x) and an initial guess or 
starting point x0, it may be iterated to get closer and closer to a zero
by using this update equation: x_i+1 = x_i - f(x_i)/f'(x_i), where f'(x)
is the derivative.

You may assume a fixed value for f(x) and f'(x), i.e. sin(x) and
cos(x).  Write your predicate as zero(X,Y), where X is an input guess,
and Y is the output value, iterated to be within some threshold of
zero, e.g. -0.0001<sin(Y)<0.0001.  Of course, the zeros of this
function are expected to be 0, pi, 2*pi, etc.  So the query zero(3,Y)
should return Y=3.1415, and zero(10,Y) should return Y=9.4248.


4. Using the following database, write a Prolog query to find all the
surgeons who live in Texas and make over $100,000/yr.  You might have
to add some additional data, such as about different types of
surgeons, or city-state relationships.

occupation(joe,oral_surgeon).
occupation(sam,patent_laywer).
occupation(bill,trial_laywer).
occupation(cindy,investment_banker).
occupation(joan,civil_laywer).
occupation(len,plastic_surgeon).
occupation(lance,heart_surgeon).
occupation(frank,brain_surgeon).
occupation(charlie,plastic_surgeon).
occupation(lisa,oral_surgeon).

address(joe,houston).
address(sam,pittsburgh).
address(bill,dallas).
address(cindy,omaha).
address(joan,chicago).
address(len,college_station).
address(lance,los_angeles).
address(frank,dallas).
address(charlie,houston).
address(lisa,san_antonio).

salary(joe,50000).
salary(sam,150000).
salary(bill,200000).
salary(cindy,140000).
salary(joan,80000).
salary(len,70000).
salary(lance,650000).
salary(frank,85000).
salary(charlie,120000).
salary(lisa,190000).

5. Write a predicate to generate all bit vectors of a specified length:

  ?- bitvec(3,K).
  K = [0, 0, 0] ;
  K = [0, 0, 1] ;
  K = [0, 1, 0] ;
  K = [0, 1, 1] ;
  K = [1, 0, 0] ;
  K = [1, 0, 1] ;
  K = [1, 1, 0] ;
  K = [1, 1, 1] ;
  No

Use this to generate 'coded' bit vectors, such as all those bit
vectors of length 5 with exactly 2 bits on. (This is a common system
used in bar-coding systems, such as on store products or postal mail,
where each code is represented by a pattern of bars of alternating
width or height and represents a different digit).

  ?- code(5,2,X).
  X = [0, 0, 0, 1, 1] ;
  X = [0, 0, 1, 0, 1] ;
  X = [0, 0, 1, 1, 0] ;
  X = [0, 1, 0, 0, 1] ;
  X = [0, 1, 0, 1, 0] ;
  X = [0, 1, 1, 0, 0] ;
  X = [1, 0, 0, 0, 1] ;
  X = [1, 0, 0, 1, 0] ;
  X = [1, 0, 1, 0, 0] ;
  X = [1, 1, 0, 0, 0] ;
  No

6. SEND + MORE = MONEY is a classical ``crypto-arithmetic'' puzzle: the
variables S, E, N, D, M, O, R, Y represent digits between 0 and 9, and
the task is finding values for them such that the following arithmetic
operation is correct:

     S  E  N  D
+    M  O  R  E
----------------
  M  O  N  E  Y

Moreover, all variables must take unique values, and all the numbers
must be well-formed (which implies that M > 0 and S > 0).