Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: zz-x2580
COMP9020 Assignment
Objectives and Outcomes
The purpose of this assignment is to build your mathematical maturity in the areas of Recursion, Logic and
Graph Theory and to reinforce the concepts covered earlier in the course. Most questions are presented at a
highly abstract level so that the consequences are very general, and can be applied in a variety of situations:
not just later on in the course, but also beyond. The specific motivation for each problem can be summarised
as follows:
Problem 1: This question works through an inductive construction of the reflexive, transitive closure of a re-
lation R. For any binary relation R, the reflexive transitive closure of R, denoted R∗, is defined as the
smallest (with respect to ⊆) relation which contains R and is reflexive and transitive. It is closely con-
nected to the Kleene star operation seen in formal languages – both R∗ and Σ∗ are what are known as
free monoids (generated by R and Σ respectively). However, the main purpose of this question is to prove
several results about recursively defined objects (using, for example, induction).
Problem 2: This question presents an alternative, recursive perspective on a data structure that may be en-
countered in other courses – the tree data structure. Such a perspective makes it easier to write recursive
programs (or functions) for various operations on the structure (e.g. counting nodes of various types).
Advantages of doing this can be seen in the last part of the question where we prove that there is a
(unsurprising, given Quiz 5 Question M4) connection between two programs/functions. Note that the
question is asking you to prove the relationship between the functions defined in the question – not that
this property holds in trees.
Problem 3: This question looks at the complexity of three algorithms for various matrix operations – two
iterative algorithms for matrix addition and multiplication and one recursive algorithm for matrix mul-
tiplication. This recursive algorithm takes the first steps towards the Strassen Algorithm for matrix
multiplication. In that algorithm, the recursive submatrices (SW + TY, etc) are cleverly computed via
a different set of intermediate matrix calculations (e.g. one step is to calculate (S + V)(W + Z)) rather
than the more direct approach we take here. The Strassen Algorithm is also closely related to the Karat-
suba algorithm for integer multiplication – an elementary form of this is taught in primary school as
the Box method.
Problem 4: In this question we revisit Question 9 from the first assignment and this time model a “real-
world” problem using Propositional Logic rather than Graph Theory.
Problem 5:
Problem 6:
After completing this assignment, you will:
• Be able to make rigorous arguments about the foundational structures used in discrete mathematics
[Problems 1, 3, 6]
• Be able to make rigorous arguments about fundamental Computer Science concepts of recursion, in-
duction and algorithmic analysis [Problems 1, 2, 3, 5, 6]
• Be able to understand and apply the concepts of Boolean and propositional logic [Problems 4, 5]
• Be able to make rigorous arguments while applying concepts from combinatorics, probability and statis-
tics [Problems 5, 6]
• Be able to create and reason about abstract models of concrete (“real-world”) problems and objects
[Problems 4, 6]
• Understand several deeper connections between different topics of the course [Problems 1, 3, 4, 5, 6]
Due: Wednesday, 22nd November, 12:00 noon (AEDST)
1
Submission is through inspera. Prose should be typed, not handwritten.
Discussion of assignment material with others is permitted, but the work submitted must be your
own in line with the University’s plagiarism policy.
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 in inspera.
• 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 referenced1 – however, answers that depend too heavily on
external resources may not receive full marks if you have not adequately demonstrated ability/un-
derstanding.
• Questions have been given an indicative difficulty level:
Pass Credit Distinction High distinction
This should be taken as a guide only. Partial marks are available in all questions, and achievable by
students of all abilities.
1Proper 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.
2
Specific advice on how to do this assignment
Problem 1
• To best gain an intuitive understanding of what Rn represents, consider the graphical representation
of R. Let us call an edge in the graphical representation of R, an “R-step”. For example with the
relation R = {(1, 1), (2, 3), (3, 2)} from the lectures we have an R-step from 2 to 3, an R-step from 3
to 2 and an R-step from 1 to 1. In other words, the relation R relates x and y if there is an R-step
from x to y. Building on this we have:
– The identity relation I = R0 only relates elements of S to themselves – so we can say that it
relates x and y if there are 0 R-steps between them.
– Therefore, the relation R1 = I ∪ R relates x and y if there are 0 or 1 R-steps between them.
– With some inductive reasoning, it is not hard to see that in general, Rn relates x to y if there are
at most n R-steps between them
• Based on this intuition, it should be obvious why the results of (a) and (b) hold, but these questions
are looking for a formal proof. Induction is not required, but it is a strongly recommended approach.
Here is an example of an HD-level induction proof, proving that the sum of the first n odd numbers
is equal to n2:
Let P(n) be the proposition that:
n
∑
i=1
(2i− 1) = n2.
We will prove that P(n) holds for all n ∈N by induction on n.
Base case: n = 0
Here we have
0
∑
i=1
(2i− 1) = 0 = 02,
so P(0) is true.
Inductive case: P(n)⇒ P(n + 1)
Assume that P(n) holds for some n ∈N. That is,
n
∑
i=1
(2i− 1) = n2.
Then
∑n+1i=1 (2i− 1) = ∑ni=1(2i− 1) + 2(n + 1)− 1
= n2 + 2n + 1 (IH)
= (n + 1)2.
Therefore P(n + 1) holds.
Conclusion.
We have P(0) holds, and if P(n) holds then P(n + 1) holds. Therefore, by induction, P(n)
holds for all n ∈N.
3
• Part (a) shows that the sequence R0, R1, R2, . . . is increasing (with respect to ⊆). For (c) you are being
asked to show that if there is a point where the sequence does not strictly increase, then it will never
change from that point onwards. Because this needs to be shown for an infinite number of cases,
again an induction proof is recommended. Be sure to clearly state the proposition you are trying to
prove.
• In part (c) there is no guarantee that such an i necessarily exists (indeed, for infinite sets S it is
possible that there is no such i). Part (d) shows that for finite sets with k elements, taking i = k2 is
such a point where Ri = Ri+1. It is in fact true for smaller i (e.g. i = k), but the proof with k2 is
easier. As a hint, what set has size k2? And make use of part (a) to show that |Rk2 | = |Rk2+1|.
• For (e), how to show a relation is transitive is demonstrated in the hints for Problem 1. As a hint for
how to proceed: use (b), (c) and the defintion of relational composition (;).
• For part (f) you need to show that if T ⊆ S × S is a reflexive, transitive relation, and R ⊆ T then
Rk
2 ⊆ T. One way to do this is to show that Ri ⊆ T for all i. Some results that may help with this
(which need to be proven):
– R1; (R2 ∪ R3) = (R1; R2)∪ (R1; R3): There is a good proof of this using Assignment 1 Q8(c) and
the fact that (R ∪ S)← = R← ∪ S←.
– If X, Y ⊆ Z then X; Y ⊆ X; Z ⊆ Z; Z: Hint: use the fact that A ⊆ B if and only if A ∪ B = B.
– If T is reflexive, then I ⊆ T.
– If T is transitive, then T = T; T.
Problem 2
• The abstract definition of a binary tree is similar to the abstract definition of a linked list – except we
have two “tails”, and no data item in the head. Visually, it may be useful to think of the recursive
case as:
Tleft Tright
• An implementation of the functions count, leaves and internal in the programming language of your
choice, rather than as an abstract mathematical function, is acceptable and will not incur any penal-
ties. However, such an answer for (b) and (c) will make it almost impossible to provide a suitable
answer for part (d) (see comments below).
• Here are two examples of recursively defined functions for computing the length of a linked list,
and concatenating two linked lists (compare to the definition given in lectures of similar functions
for words):
length(L) =
{
0 if L is empty (length.B)
1 + length(L′) if L = (d, L′) (length.R)
4
concat(L1, L2) =
{
L2 if L1 is empty (concat.B)
(d, concat(L′, L2)) if L1 = (d, L′) (concat.R)
• For a distinction level answer or higher, a short (one or two sentence) justification for correctness is
expected. Here is an example of an HD-level answer giving a recursive definition for computing the
height of a binary tree: the length of the longest path from the root to a leaf (and defined to be −1
for the empty tree):
– For a non-empty tree T = (Tleft, Tright), where Tleft and Tright are not both τ, the longest
path from the root, r, to a leaf will either consist of an edge from r to the longest
path from root to leaf in Tleft, or from r to the longest path from root to leaf in Tright.
Therefore, height(T) = 1 + max{height(Tleft), height(Tright)}.
– If T = (τ, τ) then the root of T is also a leaf, so T has height 0, which, because
height(τ) = −1, can also be expressed as 1 + max{height(Tleft), height(Tright)}.
Therefore, the function height can be recursively defined as follows:
height(T) =
{ −1 if T = τ (height.B)
1 + max{height(Tleft), height(Tleft)} if T = (Tleft, Tright) (height.R)
• Instead of providing justification as above, it may be worth checking your answer against the ex-
ample tree given in the assignment description. Indeed, such a check would demonstrate a level of
understanding expected of a credit-level student, so partial marks are available for a check like the
following:
The longest path from root to leaf in the example tree has length 2, so the tree has height 2.
We can see the correctness of the previously defined height function for this tree as follows:
height(τ) = −1 (height.B)
So, height(T3) = height(T4) = height(T5) = 1 + max{height(τ), height(τ)} (height.R)
= 1 + max{−1,−1}
= 0.
So, height(T2) = 1 + max{height(T5), height(τ)} (height.R)
= 1 + max{0,−1}
= 1,
and height(T1) = 1 + max{height(T3), height(T4)} (height.R)
= 1 + max{0, 0}
= 1.
So, height(T) = 1 + max{height(T1), height(T2)} (height.R)
= 1 + max{1, 1}
= 2.
• Even though the recursive definition of binary trees consist of one base case and one recursive case,
some of the functions in parts (a)–(c) involve other cases: in particular additional base cases/special
5
cases of the recursive case (it is not important which category it falls under).
• Part (d) is about proving the specified relationship between the functions you have defined, it is not
about showing a particular property of binary trees (i.e. that the number of leaves is one more than
the number of fully-internal nodes). In particular, your proof should be relying on the definitions of
leaves and internal provided in parts (b) and (c) [and the recursive definition of binary trees on which
these are based]. An induction proof based on “the number of nodes in the tree” is unlikely to be
proving the correct result. As we are proving a result for an infinite set of structured objects, proof
by structural induction is a recommended approach. Here is an example of an HD-level structural
induction proof involving the functions length and concat defined above:
For a linked list L, let P(L) be the proposition that:
For any linked list L′: length(concat(L, L′)) = length(L) + length(L′).
We will prove that P(L) holds for all linked lists L by structural induction on L.
Base case: L is empty.
In this case we have, for any linked list L′:
length(concat(L, L′)) = length(L′) (concat.B)
= 0 + length(L′)
= length(L) + length(L′) (length.B)
Therefore P(L) holds when L is empty.
Inductive case: L = (d, L1) and P(L1) implies P(L)
Assume that P(L1) holds. That is:
For any linked list L′: length(concat(L1, L′)) = length(L1) + length(L′) (IH)
Then, for any linked list L′ we have:
length(concat(L, L′)) = length ((d, concat(L1, L′))) (concat.R)
= 1 + length(concat(L1, L′)) (length.R)
= 1 + length(L1) + length(L′) (IH)
= length ((d, L1)) + length(L′) (length.R)
= length(L) + length(L′)
So P(L) holds.
Conclusion .
We have P(L) holds when L is empty, and if P(L1) holds, then P ((d, L1)) holds. Therefore,
by structural induction, P(L) holds for all linked lists L.
• Note that when using structural induction, the induction hypothesis is that the proposition holds
for all smaller structures required to construct the complex structure. For example, when trying to
prove P(T) when T = (Tleft, Tright) the standard inductive step would be to show:
If P(Tleft) and P(Tright) both hold, then P(T) holds.
