COMP9020 Assignment 3 2021 Term 2
Due: Thursday, 12th July, 12:00 (AEST)
Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. 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 (12 marks)
Consider the following two algorithms that naïvely compute the sum and product of two n× n matrices.
sum(A,B): product(A,B):
for i ∈ [0, n): for i ∈ [0, n):
for j ∈ [0, n): for j ∈ [0, n):
C[i, j] = A[i, j] + B[i, j] C[i, j] = add{A[i, k] ∗ B[k, j] : k ∈ [0, n)}
end for end for
end for end for
return C return C
Assuming that adding and multiplying matrix elements can be carried out in O(1) time, and add will add
the elements of a set S in O(|S|) time:
(a) Give an asymptotic upper bound, in terms of n, for the running time of sum. (3 marks)
(b) Give an asymptotic upper bound, in terms of n, for the running time of product. (3 marks)
When n is even, we can define a recursive procedure for multiplying two n× n matrices as follows. First,
break the matrices into smaller submatrices:
A =
(
S T
U V
)
B =
(
W X
Y Z
)
where S, T,U,V,W,X,Y,Z are n2 × n2 matrices. Then it is possible to show:
AB =
(
SW + TY SX+ TZ
UW +VY UX+VZ
)
where SW + TY, SX + TZ, etc. are sums of products of the smaller matrices. If n is a power of 2, each
smaller product (SW, TY, etc) can be computed recursively, until the product of 1× 1 matrices needs to
be computed – which is nothing more than a simple multiplication, taking O(1) time.
Assume n is a power of 2, and let T(n) be the worst-case running time for computing the product of two
n× n matrices using this method.
(c) With justification, give a recurrence equation for T(n). (4 marks)
(d) Find an asymptotic upper bound for T(n). (2 marks)
1
Problem 2 (12 marks)
This is the Petersen graph:
0
1
2 3
4
5
6
7 8
9
(a) Give an argument to show that the Petersen graph does not contain a subdivision of K5. (6 marks)
(b) Show that the Petersen graph contains a subdivision of K3,3. (6 marks)
Problem 3 (22 marks)
Consider the following arrangement of five houses in a cul-de-sac:
For the purpose of this question we assume that:
• House 1’s neighbours are House 5 and House 2,
• House 2’s neighbours are House 1 and House 3,
• House 3’s neighbours are House 2 and House 4,
• House 4’s neighbours are House 3 and House 5, and
• House 5’s neighbours are House 4 and House 1.
The neighbourhood has decided that they are going to paint their houses, but the painting must be done
subject to the following rules:
2
• Every house is to be painted either all red or all blue.
• If two houses have the same colour, then they must be neighbours.
Your task is to prove in two different ways that this cannot be done.
(a) Formulate the problem as a problem in propositional logic. Remember to:
(i) Define any propositional variables you need and indicate what propositions they represent. Hint:
One sensible approach uses 10 variables (4 marks)
(ii) Define any propositional formulas that are appropriate and indicate what propositions they
represent. (4 marks)
(iii) Indicate how you would solve the problem (or show that it cannot be done) using propositional
logic. It is sufficient to explain the method, you do not need to provide a solution. (4 marks)
(b) Formulate the problem as a problem in graph theory. Remember to:
(i) Clearly define the vertices and edges of your graph. (4 marks)
(ii) State the associated graph problem that you need to solve. (2 marks)
(iii) Provide an argument that shows it cannot be done. (4 marks)
Problem 4 (12 marks)
Prove the following results hold in all Boolean Algebras:
(a) For all x: (x ∧ 1′) ∨ (x′ ∧ 1) = x′ (4 marks)
(b) For all x, y: (x ∧ y) ∨ x = x (4 marks)
(c) For all x, y: y′ ∧ ((x ∨ y) ∧ x′) = 0 (4 marks)
Problem 5 (16 marks)
Prove or disprove the following logical equivalences:
(a) ¬(p→ q) ≡ (¬p→ ¬q) (4 marks)
(b) ((p ∧ q)→ r) ≡ (p→ (q→ r)) (4 marks)
(c) ((p→ q)→ r) ≡ (p→ (q→ r)) (4 marks)
(d) ((p ∨ (q ∨ r)) ∧ (r ∨ p)) ≡ ((p ∧ q) ∨ (r ∨ p)) (4 marks)
Problem 6∗ (6 marks)
Show that there are no three element Boolean Algebras.
3
Problem 7 (20 marks)
Recall from Assignment 2 the definition of a binary tree data structure: either an empty tree, or a node
with two children that are trees.
Let T(n) denote the number of binary trees with n nodes. For example T(3) = 5 because there are five
binary trees with three nodes:
(a) Using the recursive definition of a binary tree structure, or otherwise, derive a recurrence equation for
T(n). (8 marks)
A full binary tree is a non-empty binary tree where every node has either two non-empty children (i.e. is
a fully-internal node) or two empty children (i.e. is a leaf).
(b) Using observations from Assignment 2, or otherwise, explain why a full binary tree must have an odd
number of nodes. (4 marks)
(c) Let B(n) denote the number of full binary trees with n nodes. Derive an expression for B(n), involving
T(n′) where n′ ≤ n. Hint: Relate the internal nodes of a full binary tree to T(n). (4 marks)
A well-formed formula is in Negated normal form if it consists of just ∧, ∨, and literals (i.e. propositional
variables or negations of propositional variables). For example, (p∨ (¬q∧¬r)) is in negated normal form;
but (p ∨ ¬(q ∨ r)) is not.
Let F(n) denote the number of well-formed, negated normal form formulas1 there are that use precisely
n propositional variables exactly one time each. So F(1) = 2, F(2) = 16, and F(4) = 15360.
(d) Using your answer for part (c), give an expression for F(n). (4 marks)
Remark
The T(n) are known as the Catalan numbers. As this question demonstrates they are very useful
for counting various tree-like structures.
1Note: we do not assume ∧ and ∨ are associative
4
Advice on how to do the assignment
Collaboration is encouraged, but all submitted work must be done individually without consulting some-
one else’s solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.
• Assignments are to be submitted via WebCMS (or give) as a single pdf file.
• When giving answers to questions, we always would like you to prove/explain/motivate your an-
swers. You are being assessed on your understanding and ability.
• Be careful with giving multiple or alternative answers. If you give multiple answers, then we will
give you marks only for your worst answer, as this indicates how well you understood the question.
• Some of the questions are very easy (with the help of external resources). You may make use of
external material provided it is properly referenced2 – however, answers that depend too heavily on
external resources may not receive full marks if you have not adequately demonstrated ability/un-
derstanding.
2Proper referencing means sufficient information for a marker to access the material. Results from the lectures or textbook can be
used without proof, but should still be referenced.
5

欢迎咨询51作业君