COMP2111 Assignment 1 2019 Term 1

COMP2111 Assignment 1 2019 Term 1
Due: Monday, 18th March, 23:59
Submission is through WebCMS/give and should be a single pdf file, maximum size 4Mb. Prose should
be typed, not handwritten. Use of LATEX is encouraged, but not required.
Discussion of assignment material with others is permitted, but the work submitted must be your own in
line with the University’s plagiarism policy.
Problem 1 (20 marks)
Given two sets A and B, we define the operation  as follows:
A  B := (A \ B)c.
Answer the following questions using the Laws of Set Operations (and any related results proven in
lectures or tutorials) to justify your answer:
(a) What is (A  B)  (A  B)? (5 marks)
(b) Express Ac using only A,  and parentheses (if necessary). (5 marks)
(c) Express A [ B using only A, B,  and parentheses (if necessary). (10 marks)
Problem 2 (20 marks)
A binary tree is a data structure where each node is linked to at most two successor nodes:
If we allow empty binary trees (trees with no nodes), then we can simplify the possibilities of zero, one,
or two successors by saying a node has exactly two children which are binary trees.
(a) Give a recursive definition of the binary tree data structure. Your definition may be concrete (i.e. code)
or abstract, as long as it is clear what the base and recursive cases are. (4 marks)
A leaf in a binary tree is a node that has no successors (i.e. it has two empty trees as children). A fullyinternal
node in a binary tree is a node that has two successors.
1
Created in Master PDF Editor
(b) Based on your recursive definition above, define (in code or mathematically) the function leaves(T)
that counts the number of leaves in a binary tree T. (4 marks)
(c) Based on your recursive definition above, define (in code or mathematically) the function internal(T)
that counts the number of fully-internal nodes in a binary tree T. Hint: it is acceptable to define an empty
tree as having ?1 fully-internal nodes. (4 marks)
(d) If T is a binary tree, let P(T) be the proposition that leaves(T) = 1+internal(T). Prove that P(T) holds
for all binary trees T. (8 marks)
Problem 3 (20 marks)
Four wifi networks, Alpha, Bravo, Charlie and Delta, all exist within close proximity to one another as
shown below.
Alpha Bravo Charlie Delta
Networks connected with an edge in the diagram above can interfere with each other. To avoid interference
networks can operate on one of two channels, hi and lo. Networks operating on different channels will not
interfere; and neither will networks that are not connected with an edge.
Our goal is to determine (algorithmically) whether there is an assignment of channels to networks so
that there is no interference. To do this we will transform the problem into a problem of determining if a
propositional formula can be satisfied.
(a) Carefully defining the propositional variables you are using, write propositional formulas for each of
the following requirements:
(i) j1: Alpha uses channel hi or channel lo; and so does Bravo, Charlie and Delta. (4 marks)
(ii) j2: Alpha does not use both channel hi and lo; and the same for Bravo, Charlie and Delta.(4 marks)
(iii) j3: Alpha and Bravo do not use the same channel; and the same applies for all other pairs of
networks connected with an edge. (4 marks)
(b) (i) Show that j1 ^ j2 ^ j3 is satisfiable; so the requirements can all be met. Note that it is sufficient
to give a satisfying truth assignment, you do not have to list all possible combinations. (4 marks)
(ii) Based on your answer to the previous question, which channels should each network use in order
to avoid interference? (4 marks)
Problem 4 (20 marks)
Prove the following arguments are valid using Natural Deduction:
(a) A _ (B ^ C), A ! C ` C (10 marks)
(b) :(P ! Q) ` P (10 marks)
2
Created in Master PDF Editor