CS314, Summer 2008
Homework 4

Question 1. 40 points

Given a set of facts about webpages and their links, write a Prolog program that
can answer queries about ALL the pages reachable from a certain webpage, or about
all the pages pointing (directly or indirectly) to a certain webpage.

link(yahoo,cnn).
link(cnn,latimes).
link(cnn,bbc).
link(cnn,nytimes).
link(google,nytimes).
link(latimes,unitedmedia).
link(blogger,unitedmedia).

Code the predicate findpath(X,Y) which returns Y a webpage directly or indirectly
reachable from X.

Is your definition invertible?  In other words, can you specify a Y and find all pages
directly or indirectly linking to it.

Question 2. 60 points

Using lists to represent sets.  

a. Implement a predicate, intersect that computes the intersection of two sets.  


e.g., intersect([1,2,3,4],[1,4,5],Ret)

Ret = [1,4]


b. Implement a predicate, union that computes the union of two sets.  Insure that the 
union contains no duplicates.


e.g., union([1,2,3,4],[1,4,5],Ret)

Ret = [1,2,3,4,5]

Question 3. Extra Credit worth 15 points

A more challenging problem.  Implement the following predicate, palin(X) which 
returns "Yes" if X is a palindrome and "No" otherwise.  Usually palindromes are
defined with strings but we will use lists of constants and numbers.  Such lists are 
palindromes if they are the same when read forwards or backwards.  Examples of 
palindromes include [a, b, a, b, a] and [1, 2, 3, 3, 2, 1]. [a, a, b, b] and 
[1, 2, 3, 4, 5] are not palindromes.  To solve the problem you will need to
break it down into subtask(s).