Homework 3, CS314, Fall 2007
Assigned Tuesday, Sept 24, 2007

This assignment will help you to get acquainted with Prolog. DO THESE
PROBLEMS. They will be discussed in recitation.during the week of
October 1st. 

1. Write the Prolog program that given a set of facts about classes
and their prerequisites can answer queries about ALL the prerequisites
for a particular course, or about ALL the course for which one course is
a prerequisite.

pre(111,112).
pre(112,113).
pre(205,113).
pre(112,314).
pre(112,336).
pre(314,416).
pre(344,416).

Code the predicate findpre(X,Y) which returns Y, a direct or indirect
prerequisite of X.

Experiment with your clauses defining findpre(X,Y). Are your rules
invertible?  Can you also ask a query findpre(111,Y) and obtain all
the courses for which 111 is a prerequisite?

2. Think of representing a set as Prolog list. Write a Prolog program
that calculates the intersection of 2 sets and the union of two sets
(Be careful: these are sets, not multisets, so you can not just use
append to accomplish the union.)

3.(more challenging) A program that given a list checks if it is a
palindrome; that is, palin(X) returns yes when X is a list that is a
palindrome and no otherwise. A palindrome is a word that is the same
when read forwards and backwards, such as mom or madam. For our
purposes, let's consider sequences of symbols or numbers to be
considered palindromes. For example, [1,2,2,1] and [a,b,c,b,a] are
palindromes whereas [1,2,3,1] and [a,b,c,b] are not.  Recall that the
way to approach this problem is to decompose each task into subtasks
and write rules to accomplish each subtask, finally composing them
together.