Specification for COMP9414 / COMP9814 Assignment 1 - 2012s1


Changes to Specification

Remember to check this section for any updates to the specification.
DateChange
5 Mar 2012Original 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 2012Question 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 2012Q5/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.


Testing Your Code

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! E-mail to the lecturer is often the most convenient way.


COMP9814-only Questions

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 http://www.cse.unsw.edu.au/~billw#contact .


  1. Write a predicate 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 that 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 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.


  1. For the purposes of the examples in this question, assume that the following facts have been loaded into Prolog:
    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.


  1. 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. 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 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.


  1. Write a predicate 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.
    


  1. Copy from the lecture notes the predicate 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.
    

    pictures of trees in tree_height examples

    Illustrations of the trees used in the examples above.


    COMP9814 only: Write a predicate 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.)


Testing

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.


Submitting your assignment

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.pl
where 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.pl
where 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.