COMP3411/9414/9814 Project 1
?- Xis log(3.7).
X = 1.308332819650179.
?- X = log(3.7).
X = log(3.7).
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.
Hint: look up univ or= .. in the Prolog Dictionary.
4. Any list of integers can (uniquely) be broken into “parity runs” where each run is a (maximal) sequence
of consecutive even or odd numbers within the original list. For example, the list
List= [8,0,4,3,7,2,-1,9,9]
can be broken into [8, 0, 4], [3, 7], [2] and [-1, 9, 9]
Write a predicate paruns(List, Runlist) that converts a list of numbers into the corresponding list of
parity runs. For example:
?- paruns([8,0,4,3,7,2,-1,9,9], Runlist).
Runlist = [ [8, 0, 4], [3, 7], [2], [-1, 9, 9]]
Note: you can find out how to test if a number is even or odd from the Prolog Dictionary
5. In this question we consider binary trees which are represented as either empty or tree(L, Num, R),
where L and R are the left and right subtrees and Num is a number.
A binary tree of numbers is called a heap (or, it is said to satisfy the heap property) if, for every non
leaf node in the tree, the number stored at that node is less than or equal to the number stored at each of
its children. For example, the following tree satisfies the heap property, because 3:::; 5, 5:::; 8 and 5:::; 7.
tree(empty,3,tree(tree(empty,8,empty),5,tree(empty,7,empty)))
On the other hand, the following tree does not satisfy the heap property, because 6 is not less than or
equal to 5.
tree(tree(tree(empty,4,empty),
3,tree(empty,5,empty)),6,tree(tree(empty,9,empty),7,empty))
Write a predicate is_heap(Tree) which returns true if Tree satisfies the heap property, and false
otherwise. For example:
?- is_heap(tree(tree(tree(empty,4,empty),
3,tree(empty,5,empty)),6,tree(tree(empty,9,empty),7,empty))).
false.
?- is_heap(tree(empty,3,tree(tree(empty,8,empty),5,tree(empty,7,empty)))).
true
COMP9814 only: The height of a binary tree is defined to be the number of nodes in the longest path
from the root to a leaf. A binary tree is called balanced if, for every node in the tree, the height of its
left and right subtree differ by no more than 1. For example, the tree on the left is balanced, with height
4, but the tree on the right is not balanced, because the left and right subtree of node 4 have heights 0
and 2, respectively.
2
/
4
6
\
7
2 4
/ �
/\
5
COMP9814 only: Write a predicate height_if _balanced(Tree, HiB), which takes a binary tree Tree
and binds its second argument HiB to the height of the Tree, if it is balanced, or -1 if it is not balanced.
Trees are represented as either empty or 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.
You are free to copy the predicate max(First, Second, Max) from the lecture notes and use it in your
program.
Tree must be instantiated at the time of the call. These examples use the trees shown above:
?- height_if_balanced(tree(tree(tree(empty,1,empty),2,empty),
HiB = 4;
false.
3, tree(tree(empty,4,empty),
5, tree(empty,6,tree(empty,7,empty)))),HiB).
?- height_if_balanced(tree(tree(tree(empty,1,empty),2,empty),
HiB = -1
false.
Testing
3, tree(empty,4,tree(tree(empty,5,empty),
6, tree(empty,7,empty)))),HiB).
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
7