Date  Change 
5 Mar 2012  Original question 5 removed, and so the old question 6
(tree_height , etc.) becomes the new question 5. You should
check the first paragraph of the updated spec for the (new) question 5. 
15 Mar 2012  Question 3 has been modified. It used to say that
you should write a predicate sqrt_table(N, M, Result)
that binds Result to the list of pairs consisting
of a number and its square root, from N down to
M , where N and M are
natural numbers, and N > M .
The new version changes N > M to
N >= M .

24 Mar 2012  Q5/COMP9814: tree_member : response to example query
changed from true. to
true ; false. 
This assignment is worth 10% of the assessment for COMP9414 Artificial Intelligence and/or 10% of the assessment for COMP9814 Extended Artificial Intelligence, subject to the assessment formula, which is given in the Course Introduction, linked on the class home page.
In this assignment, you are to write Prolog procedures to perform some list and tree operations. The aim of the assignment is to give you experience with typical Prolog programming techniques.
At the start of your program, place a comment containing your full name, student number and assignment name. You may add additional information like the date the program was completed, etc. if you wish.
At the start of each Prolog predicate that you write, write a comment describing the overall function of the predicate.
Advice on the use of comments and meaningful identifiers in Prolog can be found under comments in the Prolog Dictionary.
A significant part of completing this assignment will be testing the code you write to make sure that it works correctly. To do this, you will need to design test cases that exercise every part of the code.
You should pay particular attention to "boundary cases", that is,
what happens when the data you are testing with is very small, or in
some way special. For example (not all of these matter in all cases, so
for example with sqrt_table
, negative numbers don't have
square roots, so it doesn't make sense to ask whether your code works with
negative numbers):
With each question, some example test data are provided to clarify what the code is intended to do. You need to design further test data. Testing, and designing test cases, is part of the total programming task. If you are unsure what your code is supposed to do in a particular case, don't guess  ask! Email to the lecturer is often the most convenient way.
Questions marked COMP9814 only need only be answered by students enrolled in COMP9814. (Students enrolled in COMP9414 are welcome and encouraged to solve these problems but their solutions will not be assessed.)
It is important to use exactly the names given below for your predicates, otherwise the automated testing procedure will not be able to find your predicates and you will lose marks. Even the capitalisation of your predicate names must be as given below.
Please send any questions about this assignment to billw
 full email details at
http://www.cse.unsw.edu.au/~billw#contact
.
sumsq_even(Numbers, Sum)
that sums the
squares of only the even numbers in a list of nonnegative whole
numbers. Example:
? sumsq_even([1,3,5,2,4,6,8,7], Sum). Sum = 120 ; false.
Note that it is the element of the list, not its position, that should
be tested for oddness. (The example computes 2*2 + 4*4 + 6*6 +
8*8
.) Think carefully about how the predicate should behave on
the empty list — should it fail or is there a reasonable value
that Sum
can be bound to?
In order to decide whether a number is even or odd, you can use the
builtin Prolog operator N mod M
, which computes the remainder
after dividing the whole number N
by the whole number
M
. Thus a number N
is even if the goal
0 is N mod 2
succeeds. Remember that arithmetic expressions
like X + 1
and N mod M
are only evaluated,
in Prolog, if they appear after the is
operator. So
0 is N mod 2
works, but N mod 2 is 0
doesn't work.
likes(mary, apple). likes(mary, pear). likes(mary, grapes). likes(tim, mango). likes(tim, apple). likes(jane, apple). likes(jane, mango).NOTE: do not include these in your solution file.
Write a predicate all_like(What, List)
that succeeds if
List
is empty or contains only persons that like
What
, according to the predicate likes(Who,
What)
. Example:
? all_like(apple,[mary, tim]). true ; false. ? all_like(grapes,[mary, tim]). false. ? all_like(pear,[]). true ; false.
COMP9814 only: Write a predicate
all_like_find(+Object, List)
that binds List
to the list of
all persons who like Object
.
? all_like_find(mango, Who). Who = [tim, jane] ; false.
Note that your all_like
predicate will be tested with
different likes(Who, What)
facts to those in the
examples.
sqrt_table(N, M, Result)
that binds Result
to the list of pairs consisting
of a number and its square root, from N
down to
M
, where N
and M
are
natural numbers, and N >= M
. For example:
sqrt_table(7, 4, Result). Result = [[7, 2.64575], [6, 2.44949], [5, 2.23607], [4, 2.0]] ; false.Note that the Prolog builtin function sqrt computes square roots, and needs to be evaluated using
is
to
actually compute the square root:
? X is sqrt(2). X = 1.41421 ; false. ? X = sqrt(2). X = sqrt(2) ; false.
COMP9814 only: write a predicate
function_table(+N, +M, +Function, Result)
that binds Result
to the list of pairs consisting
of a number X and Function(X), from N
down to
M
. For example:
? function_table(7, 4, log, Result). Result = [[7, 1.94591], [6, 1.79176], [5, 1.60944], [4, 1.38629]] ; false.
log
computes the natural logarithm of it's argument.
remove_repeats(List, NewList)
that binds NewList
to List
with all
successive repeats of an atom removed. For example:
remove_repeats([a, b, b, c, c, c, a], Result). Result = [a, b, c, a] ; false.
max(First, Second, Max)
that, given two numbers First
and Second
,
binds Max
to the larger of the two.
Use the version of the code that does not have a cut in it.
As a matter of good practice, your header comment for max
should acknowledge where it comes from.
Using the predicate max
, write a predicate
tree_height(Tree, Max)
,
which binds its second argument Max
to the number
of nodes on the longest path
from the root to a leaf in a binary Tree
.
Trees are represented either as empty
or as tree(L, Data,
R)
, where L
and R
are the left and right
subtrees. The Data
in each node of the tree is irrelevant to
this programming exercise.
Tree
must be instantiated at the time of the
call. Example:
? tree_height(tree(tree(empty,a,empty),b,tree(empty,c,tree(empty,d,empty))), Z). Z = 3 ; false. ? tree_height(tree(tree(tree(tree(tree(tree(empty,1,empty), 2,empty),3,empty),4,empty),5,empty),6,empty), Z). Z = 6 ; false.
Illustrations of the trees used in the examples above.
tree_member(?Element,
+Tree)
that checks if an element is in a tree, very much like
member(Element, List)
. Example:
? tree_member(a, tree(tree(empty,a,empty),b,tree(empty,c,tree(empty,d,empty)))). true ; false. ? tree_member(X, tree(tree(empty, a, empty), b, tree(empty, c, tree(empty, d, empty)))). X = b ; X = a ; X = c ; X = d ; false.(In the above the user pressed
;
after each solution to ask the
Prolog engine to backtrack and find an alternative solution.)
COMP9814 only: Also write a predicate tree_findall(Data, Tree, List)
where
List
is bound to a list of all data elements of
Tree
that match Data
. Example:
? tree_findall(X, tree(tree(empty, a, empty), b, tree(empty, c, tree(empty, d, empty))), L). X = _G199 L = [b, a, c, d] true. ? tree_findall(b, tree(tree(empty, a, empty), b, tree(empty, c, tree(empty, d, empty))), L). L = [b] true.(The
_G199
in the binding X = _G199
in the
first example is arbitrary.)
Your assignment will be tested by an automated testing system, and also read by a human marker. Marks will be allocated for test results, and for layout, comments, and comprehensibility.
Your code must work under the version of SWI Prolog used on the Linux machines in the UNSW School of Computer Science and Engineering. If you develop your code on any other platform, it is your responsibility to retest and if necessary correct your code when you transfer it to a CSE Linux machine prior to submission.
Put the Prolog code for all problems into a single file for submission purposes.
Due date: Thursday of week 5 (29 March 2012) at 11.55pm
cs9414 students: To hand in, log in to a School of CSE Linux workstation or server, make sure that your program is in the current working directory, and use the Unix command:
% give cs9414 prolog mycode.plwhere
mycode.pl
is replaced by the name of the file with your
code in it.
cs9814 students: To hand in, log in to a School of CSE Linux workstation or server, make sure that your program is in the current working directory, and use the Unix command:
% give cs9414 extprolog mycode.plwhere
mycode.pl
is replaced by the name of the file with your
code in it. (Yes, that's cs9414
and extprolog
.)
Please make sure your code works on CSE's Linux machines and generates no warnings. Remove all test code from your submission, including that for question 2. Make sure you have named your predicates correctly.
Late Penalty: (as specified in the Course Introduction document) 1 mark per day off the ceiling mark, up to 5 days late (e.g. an assignment worth 7/10 handed in 3 days late will receive 7/10, 4 days late 6/10, and 5 or more days late 5/10).
This specification © Copyright  Bill Wilson, 2012
UNSW's CRICOS Provider No. is 000098G.