COMP9020 Sample exam – Solutions 2022 Term 3
Inspera link
https://moodle.telt.unsw.edu.au/mod/lti/launch.php?id=5205731
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.
Problem 6
Prove or disprove the following:
For all graphs G and H where H is a subdivision of G:
(a) The clique number of H is less than or equal to the clique number of G
(b) The chromatic number of H is less than or equal to the chromatic number of H.
Solution
(a) This is true. We observe that subdividing an edge does not introduce any cliques other than a
clique of size 2 as it introduces a new vertex with degree 2. If G has clique number 1 then it has
3
no edges, so H also has no edges and also has clique number 1. Otherwise the largest clique
in G must be larger than (or equal to) the largest clique of H. So the clique number of H is less
than or equal to the clique number of G.
(b) This is false. The 5-cycle C5 has chromatic number 3 as shown in lectures, and the 4-cycle C4
has chromatic number 2. However C5 is a subdivision of C4.
Problem 7
Give, with justification, an example of an undirected graph with 6 vertices, 9 edges which is regular and
planar.
Solution
Note that a regular graph with 6 vertices and 9 edges must have every vertex with degree 3
(because 18 = 2× 9 = ∑deg(v) = 6× deg(v)).
Consider the following graph with 6 vertices and 9 edges:
It is planar because it has been drawn in the plane without edges crossing.
It is regular because each vertex has degree 3.
Problem 8
For each of the following code snippets, provide an asymptotic upper bound for T(n), the running time
of the code.
(a)
my_func(n):
for i ∈ [0, n):
j = n
while j > 0:
for k ∈ [0, n):
print(’*’)
end for
j = j/2
end while
end for
(b)
my_func2(n):
if n = 0:
print(’*’)
else:
i = 0
while i < n:
my_func2(i)
my_func2(n− i− 1)
i = i+ n/2
end while
end if
4
Solution
(a) • Each line uses O(1) elementary operations.
• The innermost for loop runs n times, so this will use a total of O(n) × O(1) = O(n)
operations.
• The while loop runs O(log n) times, so this will take O(n log n) time in total.
• The outermost for loop runs n times, so this will take O(n) ×O(n log n) = O(n2 log n)
time.
Therefore T(n) ∈ O(n2 log n).
(b) • With the exception of the recursive calls, each line takes O(1) time.
• The while loop executes twice, so it is easiest to look at all the recursive calls individually.
We have:
– One recursive call to my_func2(0), taking T(0) = O(1) time
– One recursive call to my_func2(n-1), taking T(n− 1) time
– One recursive call to my_func2(n/2), taking T(n/2) time
– One recursive call to my_func2(n/2-1), taking T(n/2− 1) time
Therefore, we have
T(n) = T(n− 1) + T(n/2) + T(n/2− 1) +O(1); T(0) = O(1)
We cannot use the Master Theorem directly here to find an explicit bound for T(n).
Assuming T is increasing, we have T(n/2− 1) ≤ T(n/2) ≤ T(n− 1), so we can approximate
T(n) as:
T(n) ≤ 3T(n− 1) +O(1)
Using the linear form of the Master Theorem this gives T(n) ∈ O(3n).
Problem 9
Let Σ = {a, b} and define L ⊆ Σ∗ recursively as follows:
• λ ∈ L
• If w ∈ L then awb ∈ L
• If w1,w2 ∈ L then w1w2 ∈ L
a Which of the following words are in L:
• aabb
• abab
• abba
• baab
b Let P(w) be the proposition that w has the same number of a’s as b’s. Prove that P(w) holds for all
w ∈ L.
5
Solution
(a) Since λ ∈ L (first rule), we have:
• aλb = ab ∈ L (second rule)
• a(ab)b = aabb ∈ L (second rule)
• (ab)(ab) = abab ∈ L (third rule)
We observe that none of the rules let us put an a at the end of a word in L, nor a b at the start.
So abba and baab will not be elements of L.
(b) We prove P(w) holds for all w ∈ L by induction.
Base case: w = λ.
λ has the same number of a’s as b’s, so P(λ) holds.
Inductive case 1: w = aw′b where w′ ∈ L
We will show that P(w′) implies P(aw′b).
Assume w′ ∈ L and P(w′) holds. That is, w′ has the same number of a’s as b’s. Suppose w′ has
n a’s. Consider w = aw′b which is in L by the second rule. w has n+ 1 a’s and n+ 1 b’s, so it
has the same number of a’s as b’s. Therefore P(w) holds.
Inductive case 2: w = w1w2 where w1,w2 ∈ L
We will show that P(w1) and P(w2) imply P(w1w2).
Assume w1,w2 ∈ L and P(w1) and P(w2) hold. Suppose w1 has n a’s (and therefore n b’s) and
w2 has m a’s (and therefore m b’s). Then w1w2 has n+m a’s and n+m b’s. So it has the same
number of a’s as b’s. So P(w1w2) holds.
Conclusion
Every word in L is either of the form:
• λ,
• awb where w ∈ L, or
• w1w2 where w1,w2 ∈ L
By the principle of induction, we have shown that P(w) holds for all words constructed in these
ways. Therefore P(w) holds for all w ∈ L.
Problem 10
Let PF be the set of all propositional formulas.
Define f : PF → Pow(PF) by
f (ϕ) = {ψ ∈ PF : ϕ |= ψ}
Prove or disprove the following:
6
(a) For all ϕ,ψ ∈ PF: f ((ϕ ∧ ψ)) = f (ϕ) ∩ f (ψ)
(b) For all ϕ ∈ PF: f (¬ϕ) = ( f (ϕ))c
Solution
(a) This is false. Consider ϕ = p and ψ = q. We have
(p ∧ q) |= (p ∧ q)
so (p ∧ q) ∈ f ((p ∧ q)). But
p 6|= (p ∧ q)
because for the valuation v(p) = true, v(q) = false, we have v satisfies {p} but v((p ∧ q)) =
false. So (p ∧ q) /∈ f (p) ∩ f (q).
(b) This is false. We have, for any formula ψ: ψ |= >. Therefore > ∈ f (ψ) for all ψ ∈ PF. In
particular > ∈ f (¬ϕ) but > /∈ ( f (ϕ))c for all formulas ϕ.
Problem 11
Let f : B4 → B be the boolean function defined as:
f (w, x, y, z) =
{
1 if w = x and y = z
0 otherwise
Which of the following boolean functions are equal to f ?
Note
+ and · should be taken as the usual addition and multiplication on Z. | · | should be taken as the
absolute value function
(i)
(
(w&&x) || (y&&z)) || ((!w&&!x) || (!y&&!z))
(ii)
(
(1+ w+ x) · (1+ y+ z))%2
(iii) 1− ((w+ x) · (y+ z)%2)
(iv)
(
(w||x)&& (y||z))&& ((!w||!x)&& (!y||!z))
(v) max{|1− (w+ x)|, |1− (y+ z)|}
(vi) min{1− |w− x|, 1− |y− z|}
Solution
It is helpful to remember that && = min = multiplication and || = max.
(i) This is different from f when w = x = 1 and y 6= z
7
(ii) This is the same as f
(iii) This is different from f when w = x = 1 and y 6= z
(iv) This is different from f when w 6= x and y 6= z
(v) This is different from f when w = x = 0 and y 6= z
(vi) This is the same as f
Problem 12
Consider the following timetabling arrangement given in lectures:
Potions Charms Herbology Astronomy Transfiguration
Harry Ron Harry Hermione Hermione
Ron Luna George Neville Fred
Malfoy Ginny Neville Seamus Luna
The school administrator would like to know if it is possible to arrange an exam schedule where 3 (or
more) subjects can be examined at the same time without any student having a clash (i.e. two or more
exams at the same time)
Do ONE of the following:
• Explain how this can be modelled as a graph theory problem, OR
• Explain how this can be modelled as a propositional logic problem.
In particular:
• Explain how to define a suitable graph OR an appropriate set of propositional variables and formulas
to model the situation
• Describe the associated graph theory / logic problem that needs to be solved
• Indicate how you could solve the problem. You do not have to find a solution
Solution
Graph theory solution
Consider the following graph G:
• Vertices: Subjects
• Edges: An edge between two vertices if they have no students in common.
A set of subjects that can be examined at the same time is going to be a set of subjects where any
pair of subjects have no students in common. In the given graph used to model the situation, this
corresponds to a clique.
So the question of whether three subjects can be examined at the same time, amounts to asking
whether the given graph has a clique of size 3 (or greater). Thus we can solve the problem by
computing the clique number of G. If it is 3 (or larger) then the subjects can be examined.
8
Propositional logic solution
We model the solution using Propositonal logic as follows:
• Consider the following five propositional variables representing the given statements:
– P: The potions exam is held
– C: The charms exam is held
– H: The herbology exam is held
– A: The astronomy exam is held
– T: The transfiguration exam is held
• Consider the following formulas indicating clashes for various students:
– R1 = ¬(P ∧ H): Harry is in both classes so we can’t hold these exams at the same time
– R2 = ¬(P ∧ C): Ron is in both classes
– R3 = ¬(C ∧ T): Luna is in both classes
– R4 = ¬(A ∧ T): Hermione is in both classes
– R5 = ¬(H ∧ A): Neville is in both classes
• Consider the following formula indicating at least three exams are held:
R6 = (P ∧ H ∧ C) ∨ (P ∧ H ∧ A) ∨ (P ∧ C ∧ T) ∨ · · ·
(take a disjunction over all combinations of three classes).
To solve the problem, we need to find an assignment of true/false to the propositional variables
such that all the requirements R1 – R6 are met. Such an assignment would then tell us which exams
could be held so that there are no clashes (R1 – R5) and at least three exams are held (R6).
In other words, we want to know if:
ϕ = R1 ∧ R2 ∧ R3 ∧ R4 ∧ R5 ∧ R6
is satisfiable.
Problem 13
We would like to pave a 1× n rectangular path with a mix of 1× 1 and 1× 3 paving stones.
For example, if s represents a 1× 1 stone and t represents a 1× 3 stone, then possible ways of tiling a 1× 6
path include:
• ssssss
• tt
• ssst
• ssts
• tsss
9
(Note that direction matters: e.g. ssst and tsss should be considered different arrangements)
a Let P(n, k) be the number of different arrangements of paving stones that can pave a 1× n path using
exactly k 1× 3 paving stones.
Express P(n, k) either:
• in terms of combinatorial functions defined in lectures; or
• recursively (including base cases) in terms of P(n′, k′) where n′ ≤ n and k′ ≤ k.
b Let P(n) = P(n, 0) + P(n, 1) + . . . be the number of arrangements of paving stones that can pave a 1× n
rectangular path.
Find a recurrence equation for P(n) and provide, with justification, an asymptotic upper bound.
Solution
(a) Combinatorial functions solution
If we have k 1× 3 paving stones, and we are paving a 1× n path, then we will have n− 3k 1× 1
stones; and therefore (n− 3k) + k = n− 2k stones in total. So we want to count the number of
sequences of n− 2k s’s and t’s where we have exactly k t’s. We can do this by choosing which
of the n − 2k letters will be t’s and then filling the remainder with s’s. This can be done in
(n−2kk ) ways.
Recursive solution
Consider tiling a 1× n path with k 1× 3 “t” stones. We break it up into two disjoint cases:
• Either the first stone is a 1× 3 stone, and we must pave the remaining 1× (n− 3) path
using k− 1 t-stones. This can be done in P(n− 3, k− 1) ways.
• Or the first stone is a 1× 1 stone, and we must pave the remaining 1× (n− 1) path using
k t-stones. This can be done in P(n− 1, k) ways.
Therefore:
P(n, k) = P(n− 3, k− 1) + P(n− 1, k)
For the base cases, we have:
• P(n, k) = 0 if n < 3k (the path is not long enough to fit k t-stones)
• P(n, 0) = 1 (we only use s-stones).
(b) Using the same idea as the recursive solution above, we have:
• Either the first stone is a t-stone, and there are P(n− 3) ways to pave the remaining path,
or
• the first stone is an s-stone, and there are P(n− 1) ways to pave the remaining path.
Therefore
P(n) = P(n− 1) + P(n− 3)
10
and for the base cases we have P(0) = P(1) = P(2) = 1.
To find an asymptotic upper bound, we note that P(n− 3) ≤ P(n− 1) so
P(n) ≤ 2P(n− 1); P(0) = P(1) = P(2) = 1.
Using the linear-form of the Master Theorem, this gives P(n) ∈ O(2n).
Problem 14
Let (Ω, P) be a probability space.
Prove or disprove:
(a) For all events A, B ⊆ Ω: If P(A) = P(A ∩ B) then P(B) = P(A ∪ B)
(b) For all events A, B ⊆ Ω with P(A), P(B) > 0: If P(A|B) > P(A) then P(B|A) > P(B)
Solution
(a) This is true. We have, from lectures:
P(A ∪ B) = P(A) + P(B)− P(A ∩ B) = P(B) + (P(A)− P(A ∩ B))
So if P(A) = P(A ∩ B) then P(A ∪ B) = P(B) + 0.
(b)
Note
Conditional probability not examined in 2022 T3
This is true. We have
P(A|B) = P(A ∩ B)
P(B)
P(B|A) = P(A ∩ B)
P(A)
so
P(A ∩ B)
P(A)P(B)
=
P(A|B)
P(A)
=
P(B|A)
P(B)
Therefore if P(A|B) > P(A):
1 <
P(A|B)
P(A)
=
P(B|A)
P(B)
So P(B|A) > P(B).
Problem 15
Suppose we roll n fair, six-sided dice.
Let X be the random variable that indicates the maximum value of all dice.
(a) For m ∈ [1, 6] what is the probability that X ≤ m?
11
(b) In terms of n, what is the expected value of X?
Solution
(a) For X to be at most m, we need all dice to show m or less. For each die, the probability that it
shows m or less is m6 . Assuming, by default, each die is independent, we therefore have:
P(X ≤ m) = (m
6
)n
(b) X only takes values in [1, 6]. Therefore, we have:
E(X) = P(X = 1) · 1+ P(X = 2) · 2+ P(X = 3) · 3+ P(X = 4] · 4+ P(X = 5) · 5+ P(X = 6) · 6
To calculate P(X = m) we have, from (a):
P(X = m) = P(X ≤ m)− P(X ≤ m− 1) = (m
6
)n − (m− 1
6
)n
Therefore:
E(X) = 1 · (1
6
)n + 2 · ((2
6
)n − (1
6
)n) + 3 · ((3
6
)n − (2
6
)n) +
4 · ((4
6
)n − (3
6
)n) + 5 · ((5
6
)n − (4
6
)n) + 6 · ((6
6
)n − (5
6
)n)
= 6− ((1
6
)n + (
2
6
)n + (
3
6
)n + (
4
6
)n + (
5
6
)n)
12