xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

数学代写|Assignment代写 - COMP9020 Assignment 2

时间：2020-10-31

Due: Tuesday, 3rd November, 15:00 (AEDST)
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 (16 marks)
Let S be a set, and let R1, R2 ⊆ S × S be any equivalence relations on S.
(a) Show that R1 ∩ R2 is an equivalence relation. (6 marks)
(b) For x ∈ S let [x]i denote the equivalence class of x under Ri (i = 1, 2), and let [x] denote the equivalence
class of x under R1 ∩ R2. With justification, define [x] in terms of [x]1 and [x]2. (4 marks)
(c) Prove or disprove: R1 ∪ R2 is an equivalence relation. (6 marks)
Problem 2 (12 marks)
Let S be a set. Prove, or find a counterexample to disprove, the following for all binary relations R1, R2 ⊆ S × S:
(a) If R1 and R2 are reflexive then R1; R2 is reflexive. (4 marks)
(b) If R1 and R2 are symmetric then R1; R2 is symmetric. (4 marks)
(c) If R1 and R2 are transitive then R1; R2 is transitive. (4 marks)
Problem 3 (34 marks)
Let R ⊆ S × S be any binary relation on a set S. Consider the sequence of relations R0, R1, R2
, . . ., defined
as follows:
R0 := I = {(x, x) : x ∈ S}, and
Rn+1 := Rn ∪ (R; Rn) for n ≥ 0
Suppose there exists i ∈ N such that Ri = Ri+1.
(a) Prove that Rj = Ri
for all j ≥ i. (6 marks)
(b) Prove that Rj ⊆ Ri
for all j ≥ 0. (4 marks)
(c) If |S| = k, explain why Rk2 = Rk2+1
. (4 marks)
(d) Let P(n) be the proposition that for all m ∈ N: Rn; Rm = Rn+m. Prove that P(n) holds for all n ∈ N.
Hint: Use results from Assignment 1 (6 marks)
1
(e) If |S| = k, show that Rk2
is transitive. (4 marks)
(f) If |S| = k, show that (R ∪ R←)k2
is an equivalence relation. (6 marks)
(g)∗
If |S| = k show that (R ∪ R←)k2
is the minimum (with respect to ⊆) of all equivalence relations that
contain R. (4 marks)
Problem 4∗ (6 marks)
Let f(n) be defined recursively as follows:
f(0) = 0 f(n) = f(b n3 c) + 3 f(b n5 c) + n for n ≥ 1
Show that f(n) ∈ O(n).
Problem 5 (20 marks)
A binary tree is a data structure where each node is linked to at most two successor nodes:
If we include empty binary trees (trees with no nodes) as part of the definition, then we can simplify the
description of the data structure. Rather than saying a node has 0, 1, or 2 successor nodes, we can instead
say that a node has exactly two children, where a child is a binary tree. That is, we can abstractly define
the structure of a binary tree as follows:
• (B): An empty tree, τ • (R): An ordered pair (Tleft, Tright) where Tleft and Tright are trees.
So, for example, the above tree would be defined as the tree T where:
T = (T1, T2), where
T1 = (T3, T4) and T2 = (T5, τ), where
T3 = T4 = T5 = (τ, τ)
That is,
T = (τ, τ),(τ, τ), ,(τ, τ), τ A leaf in a binary tree is a node that has no successors (i.e. it is of the form (τ, τ)). A half-leaf in a binary
tree is a node that has exactly one successor (i.e. it is of the form (T, τ) or (τ, T) where T = τ). The
example above has 3 leaves (T3, T4, and T5) and 1 half-leaf (T2). For technical reasons (that will become
apparent) we assume that an empty tree has 0 leaves and 1 half-leaves.
(a) Based on the recursive definition above, recursively define a function count(T) that counts the number
of nodes in a binary tree T. (4 marks)
2
(b) Based on the recursive definition above, recursively define a function leaves(T) that counts the number
of leaves in a binary tree T. (4 marks)
(c) Based on the recursive definition above, recursively define a function half-leaves(T) that counts the
number of half-leaves in a binary tree T. (4 marks)
(d) If T is a binary tree, let P(T) be the proposition that count(T) = 2 × leaves(T) + half-leaves(T) ) 1.
Prove that P(T) holds for all binary trees T. Your proof should be based on your answers given in (a),
(b) and (c). (8 marks)
Problem 6 (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)
3
Advice on how to do the assignment
Collaboration is encouraged, but all submitted work must be done individually without consulting someone 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 answers. 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/understanding.