CSc 8710, DDLP, Fall 2010
Take Home Exam 3 - Due: December 3rd (Friday)
SUBMIT files under assignment 5 using handin8710
------------------------------------------------

(1) (50 Points) Programming Assignment 5

(2) (20 Points) Compute ALL the stable models for the following programs:

(a)

a(1,2).
a(2,3).
a(3,1).
p(X) :- a(X,Y), not q(Y).
q(X) :- a(X,Y), not p(Y).

(b)

vc(X) :- edge(X,Y), not vc(Y).
edge(1,2).
edge(1,3).
edge(2,3).
edge(2,4).
edge(3,4).

(c)

q :- p, not r.
q :- r.
p :- q, r.
p :- not r.
r :- s, not v.
s :- v.
v :- s.

(d)

p :- not q, not r.
q :- not p, s.
r :- not v.
s :- s, not v.
v :- not s.

(3) (30 Points) Apriori Algorithm - Hand Execution

A grocery store sells items coded a through z. Consider the following
transaction database:

TID  Items
--------------------
01   a, b, c, d, f
02   a, f, g
03   a, c, g, h, k
04   b, d, e, k
05   e, l, m
06   l, n, p
07   a, p, q
08   b, q, r
09   c, q, r
10   p, r, t
11   d, p, r, s, t, u
12   s, t, u
13   b, s, t, u
14   u, v, z
15   u, v, w
16   w, z

(a) Generate all large item sets of size 3 with support = 2.
(b) For each of the large item sets in (a), generate all
    association rules with a singleton on the right-hand-side
    along with their confidence values.

(4) EXTRA CREDIT (20 points)
The due date for this is December 12th midnight.

Code the Large Item Set generation part of the Apriori algorithm in Prolog. 
The database items and transactions are available in a file (say db.pl) as:

items([1,2,3,4,5]).
db([1,3,4]).
db([2,3,5]).
db([1,2,3,5]).
db([2,5]).

A sample run is shown below:

[~/public_html/8710/f05/e3][3:08pm] pl

?- ['db.pl'].
% db.pl compiled 0.00 sec, 1,276 bytes

Yes
?- ['ap.pl'].
% ap.pl compiled 0.00 sec, 5,896 bytes

Yes
?- apriori(2).
[1]
[2]
[3]
[5]
[1, 3]
[2, 3]
[2, 5]
[3, 5]
[2, 3, 5]

Yes
?- halt.

Note: The top level predicate is apriori(N) where N is the Minimum Support.