|5 Mar 2012||Original question 5 removed, and so the old question 6
|15 Mar 2012||Question 3 has been modified. It used to say that
you should write a predicate |
|24 Mar 2012||Q5/COMP9814: |
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
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! E-mail 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 e-mail details at
sumsq_even(Numbers, Sum)that sums the squares of only the even numbers in a list of non-negative 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
Sum can be bound to?
In order to decide whether a number is even or odd, you can use the
built-in 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
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
?- all_like(apple,[mary, tim]). true ; false. ?- all_like(grapes,[mary, tim]). false. ?- all_like(pear,). true ; false.
COMP9814 only: Write a predicate
List to the list of
all persons who like
?- all_like_find(mango, Who). Who = [tim, jane] ; false.
Note that your
all_like predicate will be tested with
likes(Who, What) facts to those in the
sqrt_table(N, M, Result)that binds
Resultto the list of pairs consisting of a number and its square root, from
Mare 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 built-in function sqrt computes square roots, and needs to be evaluated using
isto 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)
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.
logcomputes the natural logarithm of it's argument.
remove_repeats(List, NewList)that binds
Listwith 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
Maxto 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
maxshould acknowledge where it comes from.
Using the predicate
max, write a predicate
which binds its second argument
Max to the number
of nodes on the longest path
from the root to a leaf in a binary
Trees are represented either as
empty or as
R are the left and right
Data in each node of the tree is irrelevant to
this programming exercise.
Tree must be instantiated at the time of the
?- 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
?- 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
_G199in the binding
X = _G199in 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 re-test 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.plis 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.plis replaced by the name of the file with your code in it. (Yes, that's
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.