Hello, dear friend, you can consult us at any time if you have any questions, add  WeChat:  zz-x2580

COMP9020

Problem 1
Prove or disprove the following:
(a) For all x, y, z ∈N: If x|z and y|z then (x+ y)|z
(b) For all x, y, z ∈N>0: If x =(z) y and y =(x) z then z =(y) x
Solution
(a) This is false. Consider x = 1, y = 2 and z = 2. We have 1|2 and 2|2 but 3 - 2.
(b) This is false. Consider x = 4, y = 6 and z = 2. We have 4 =(2) 6 and 6 =(4) 2 but 2 6=(6) 4.
Problem 2
Define f : Z→ Z as f (n) = (n div 8) + (n % 8)
Prove that 7|n if and only if 7| f (n)
Solution
We have
f (n) = (n div 8) + (n % 8)
= bn
8
c+ (n− bn
8
c · 8)
= n− 7 · bn
8
c
=(7) n
So 7| f (n)− n for all n.
Therefore, for all n we have: f (n) = n+ 7k for some k, hence 7|n if and only if 7| f (n).
Problem 3
Prove, or provide a counterexample to disprove:
(a) For all sets A, B: B ∩ (A ∪ (B ∩ Ac)) = B ∪ (A ∩ (B ∪ Ac))
(b) For all sets A, B,C,D: (A× B) ∪ (C× D) = (A ∪ C)× (B ∪ D)
1
Solution
(a) This is true. We have:
B ∩ (A ∪ (B ∩ Ac)) = B ∩ ((A ∪ B) ∩ (A ∪ Ac)) (Dist.)
= B ∩ ((A ∪ B) ∩ U ) (Comp.)
= B ∩ (A ∪ B) (Ident.)
= B (Absorp.)
= B ∪ (A ∩ B) (Absorp.)
= B ∪ ((A ∩ B) ∪∅) (Ident.)
= B ∪ ((A ∩ B) ∪ (A ∩ Ac)) (Comp.)
= B ∪ (A ∩ (B ∪ Ac)) (Dist).
(b) This is false. Consider A = D = {1} and B = C = ∅.
Then A× B = C× D = ∅, so (A× B) ∪ (C× D) = ∅.
But A ∪ C = B ∪ D = {1}, so (A ∪ C)× (B ∪ D) = {(1, 1)} 6= ∅.
Problem 4
Order the following functions in increasing order of asymptotic complexity:
• n√log n
•
√
n2 log n+ 2n3
• √n(log n)
• T(n) where T(n) = 3T(n/2) + 2n; T(1) = 1
• T(n) where T(n) = T(n− 1) + log n; T(1) = 1
• T(n) where T(n) = 3T(n/3) + 2n log n; T(1) = 1
Solution
The correct order is:
1.
√
n(log n)
2. n
√
log n
3. T(n) where T(n) = T(n− 1) + log n; T(1) = 1
4. T(n) where T(n) = 3T(n/3) + 2n log n; T(1) = 1
5.
√
n2 log n+ 2n3
6. T(n) where T(n) = 3T(n/2) + 2n; T(1) = 1
We have
√
n(log n) ∈ O(n0.6), and all other functions are asymptotically bounded below by n.
For T(n) = T(n− 1) + log n, we have, by unrolling:
T(n) = log n+ log(n− 1) + log(n− 2) + . . . + log(2) + log(1) + 1
2
All terms are bounded above by log n, so T(n) ∈ O(n log n). Also, half of the terms are bounded
below by log( n2 ) = (log n)− 1, so T(n) ≥ n2 ((log n)− 1). Therefore T(n) ∈ Ω(n log n)
For T(n) = 3T(n/3) + 2n log n we have, by the Master Theorem T(n) ∈ Θ(n(log n)2).
For T(n) = 3T(n/2) + 2n we have, by the Master Theorem T(n) ∈ Θ(nlog 3). Since log 3 > 1.5 we
have that T(n) ∈ Ω(√n2 log n+ 3n3).
Problem 5
Let R ⊆ A× A be a partial order and let f : B→ A be an arbitrary function.
Define S ⊆ B× B as follows:
(x, y) ∈ S if and only if ( f (x), f (y)) ∈ R
Prove or disprove the following:
(a) If f is surjective then S is a partial order
(b) If f is injective then S is a partial order
Solution
(a) This is false. Consider A = {0} and B = {1, 2}. There is only one possible function f , given
by f (1) = f (2) = 0, and only one possible partial order R given by R = {(0, 0)} But then
S = {(1, 1), (1, 2), (2, 1), (2, 2)} and since (1, 2), (2, 1) ∈ S and 1 6= 2 we have that S is not (AS).
(b) This is true. To show that S is a partial order, we must show (R), (AS), and (T).
(R): For all x ∈ B we have ( f (x), f (x)) ∈ R by reflixivity of R. Therefore (x, x) ∈ S, so S is
reflexive.
(AS): Suppose (x, y), (y, x) ∈ S. Then ( f (x), f (y)) and ( f (y), f (x)) ∈ R. By anti-symmetry of R
we have f (x) = f (y). By injectivity of f we have x = y. So S is anti-symmetric.
(T): Suppose (x, y), (y, z) ∈ S. Then ( f (x), f (y)) and ( f (y), f (z)) ∈ R. By transitivity of R we
have ( f (x), f (z)) ∈ R. But then (x, z) ∈ S. So S is transitive.