COMP9020Sample exam – Solutions2022Term3

Inspera link

https://moodle.telt.unsw.edu.au/mod/lti/launch.php?id=5205731

Problem1

Prove or disprove the following:

(a) For allx,y,z∈N: Ifx|zandy|zthen(x+y)|z

(b) For allx,y,z∈N

>0

: Ifx=

(z)

yandy=

(x)

zthenz=

(y)

x

Solution

(a) This is false. Considerx=1,y=2 andz=2. We have 1|2 and 2|2 but 3-2.

(b) This is false. Considerx=4,y=6 andz=2. We have 4=

(2)

6 and 6=

(4)

2 but 26=

(6)

4.

Problem2

Definef:Z→Zasf(n) = (ndiv8) + (n% 8)

Prove that 7|nif and only if 7|f(n)

Solution

We have

f(n) = (ndiv8) + (n% 8)

=b

n

8

c+ (n−b

n

8

c·8)

=n−7·b

n

8

c

=

(7)

n

So 7|f(n)−nfor alln.

Therefore, for allnwe have:f(n) =n+7kfor somek, hence 7|nif and only if 7|f(n).

Problem3

Prove, or provide a counterexample to disprove:

(a) For all setsA,B:B∩(A∪(B∩A

c

)) =B∪(A∩(B∪A

c

))

(b) For all setsA,B,C,D:(A×B)∪(C×D) = (A∪C)×(B∪D)

1

Solution

(a) This is true. We have:

B∩(A∪(B∩A

c

)) =B∩((A∪B)∩(A∪A

c

))(Dist.)

=B∩((A∪B)∩U)(Comp.)

=B∩(A∪B)(Ident.)

=B(Absorp.)

=B∪(A∩B)(Absorp.)

=B∪((A∩B)∪∅)(Ident.)

=B∪((A∩B)∪(A∩A

c

))(Comp.)

=B∪(A∩(B∪A

c

))(Dist).

(b) This is false. ConsiderA=D={1}andB=C=∅.

ThenA×B=C×D=∅, so(A×B)∪(C×D) =∅.

ButA∪C=B∪D={1}, so(A∪C)×(B∪D) ={(1, 1)}6=∅.

Problem4

Order the following functions inincreasingorder of asymptotic complexity:

•n

√

logn

•

√

n

2

logn+2n

3

•

√

n(logn)

•T(n)whereT(n) =3T(n/2) +2n;T(1) =1

•T(n)whereT(n) =T(n−1) +logn;T(1) =1

•T(n)whereT(n) =3T(n/3) +2nlogn;T(1) =1

Solution

The correct order is:

1.

√

n(logn)

2.n

√

logn

3.T(n)whereT(n) =T(n−1) +logn;T(1) =1

4.T(n)whereT(n) =3T(n/3) +2nlogn;T(1) =1

5.

√

n

2

logn+2n

3

6.T(n)whereT(n) =3T(n/2) +2n;T(1) =1

We have

√

n(logn)∈O(n

0.6

), and all other functions are asymptotically bounded below byn.

ForT(n) =T(n−1) +logn, we have, by unrolling:

T(n) =logn+log(n−1) +log(n−2) +. . .+log(2) +log(1) +1

2

All terms are bounded above by logn, soT(n)∈O(nlogn). Also, half of the terms are bounded

below by log(

n

2

) = (logn)−1, soT(n)≥

n

2

((logn)−1). ThereforeT(n)∈Ω(nlogn)

ForT(n) =3T(n/3) +2nlognwe have, by the Master TheoremT(n)∈Θ(n(logn)

2

).

ForT(n) =3T(n/2) +2nwe have, by the Master TheoremT(n)∈Θ(n

log 3

). Since log 3>1.5 we

have thatT(n)∈Ω(

√

n

2

logn+3n

3

).

Problem5

LetR⊆A×Abe a partial order and letf:B→Abe an arbitrary function.

DefineS⊆B×Bas follows:

(x,y)∈Sif and only if(f(x),f(y))∈R

Prove or disprove the following:

(a) Iffis surjective thenSis a partial order

(b) Iffis injective thenSis a partial order

Solution

(a) This is false. ConsiderA={0}andB={1, 2}. There is only one possible functionf, given

byf(1) =f(2) =0, and only one possible partial orderRgiven byR={(0, 0)}But then

S={(1, 1),(1, 2),(2, 1),(2, 2)}and since(1, 2),(2, 1)∈Sand 16=2 we have thatSis not (AS).

(b) This is true. To show that S is a partial order, we must show (R), (AS), and (T).

(R): For allx∈Bwe have(f(x),f(x))∈Rby reflixivity ofR. Therefore(x,x)∈S, soSis

reflexive.

(AS): Suppose(x,y),(y,x)∈S. Then(f(x),f(y))and(f(y),f(x))∈R. By anti-symmetry ofR

we havef(x) =f(y). By injectivity offwe havex=y. SoSis anti-symmetric.

(T): Suppose(x,y),(y,z)∈S. Then(f(x),f(y))and(f(y),f(z))∈R. By transitivity ofRwe

have(f(x),f(z))∈R. But then(x,z)∈S. SoSis transitive.

Problem6

Prove or disprove the following:

For all graphsGandHwhereHis a subdivision ofG:

(a) The clique number ofHis less than or equal to the clique number ofG

(b) The chromatic number ofHis less than or equal to the chromatic number ofH.

Solution

(a) This is true. We observe that subdividing an edge does not introduce any cliques other than a

clique of size2as it introduces a new vertex with degree2. IfGhas clique number1then it has

3

no edges, soHalso has no edges and also has clique number 1. Otherwise the largest clique

inGmust be larger than (or equal to) the largest clique ofH. So the clique number ofHis less

than or equal to the clique number ofG.

(b) This is false. The5-cycleC

5

has chromatic number 3 as shown in lectures, and the4-cycleC

4

has chromatic number 2. HoweverC

5

is a subdivision ofC

4

.

Problem7

Give, with justification, an example of an undirected graph with6vertices,9edges which is regular and

planar.

Solution

Note that a regular graph with6vertices and9edges must have every vertex with degree3

(because 18=2×9=

∑

deg(v) =6×deg(v)).

Consider the following graph with6vertices and9edges:

It is planar because it has been drawn in the plane without edges crossing.

It is regular because each vertex has degree3.

Problem8

For each of the following code snippets, provide an asymptotic upper bound forT(n), the running time

of the code.

(a)

my_func(n):

fori∈[0,n):

j=n

whilej>0:

fork∈[0,n):

print(’*’)

end for

j=j/2

end while

end for

(b)

my_func2(n):

ifn=0:

print(’*’)

else:

i=0

whilei

my_func2(i)

my_func2(n−i−1)

i=i+n/2

end while

end if

4

Solution

(a)•Each line usesO(1)elementary operations.

•The innermostforloop runsntimes, so this will use a total ofO(n)×O(1) =O(n)

operations.

•Thewhileloop runsO(logn)times, so this will takeO(nlogn)time in total.

•The outermostforloop runsntimes, so this will takeO(n)×O(nlogn) =O(n

2

logn)

time.

ThereforeT(n)∈O(n

2

logn).

(b)•With the exception of the recursive calls, each line takesO(1)time.

•Thewhileloop executes twice, so it is easiest to look at all the recursive calls individually.

We have:

–One recursive call tomy_func2(0), takingT(0) =O(1)time

–One recursive call tomy_func2(n-1), takingT(n−1)time

–One recursive call tomy_func2(n/2), takingT(n/2)time

–One recursive call tomy_func2(n/2-1), takingT(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 forT(n).

AssumingTis increasing, we haveT(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 givesT(n)∈O(3

n

).

Problem9

LetΣ={a,b}and defineL⊆Σ

∗

recursively as follows:

•λ∈L

•Ifw∈Lthenawb∈L

•Ifw

1

,w

2

∈Lthenw

1

w

2

∈L

a Which of the following words are inL:

•aabb

•abab

•abba

•baab

b LetP(w)be the proposition thatwhas the same number ofa’s asb’s. Prove thatP(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 anaat the end of a word inL, nor abat the start.

Soabbaandbaabwill not be elements ofL.

(b) We proveP(w)holds for allw∈Lby induction.

Base case:w=λ.

λhas the same number ofa’s asb’s, soP(λ)holds.

Inductive case1:w=aw

′

bwherew

′

∈L

We will show thatP(w

′

)impliesP(aw

′

b).

Assumew

′

∈LandP(w

′

)holds. That is,w

′

has the same number ofa’s asb’s. Supposew

′

has

n a’s. Considerw=aw

′

bwhich is inLby the second rule.whasn+1a’s andn+1b’s, so it

has the same number ofa’s asb’s. ThereforeP(w)holds.

Inductive case2:w=w

1

w

2

wherew

1

,w

2

∈L

We will show thatP(w

1

)andP(w

2

)implyP(w

1

w

2

).

Assumew

1

,w

2

∈LandP(w

1

)andP(w

2

)hold. Supposew

1

hasn a’s (and thereforen b’s) and

w

2

hasm a’s (and thereforem b’s). Thenw

1

w

2

hasn+m a’s andn+m b’s. So it has the same

number ofa’s asb’s. SoP(w

1

w

2

)holds.

Conclusion

Every word inLis either of the form:

•λ,

•awbwherew∈L, or

•w

1

w

2

wherew

1

,w

2

∈L

By the principle of induction, we have shown thatP(w)holds for all words constructed in these

ways. ThereforeP(w)holds for allw∈L.

Problem10

LetPFbe the set of all propositional formulas.

Definef: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φ=pandψ=q. We have

(p∧q)|= (p∧q)

so(p∧q)∈f((p∧q)). But

p6|= (p∧q)

because for the valuationv(p) =true,v(q) =false, we havevsatisfies{p}butv((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φ.

Problem11

Letf:B

4

→Bbe the boolean function defined as:

f(w,x,y,z) =

{

1ifw=xandy=z

0otherwise

Which of the following boolean functions are equal tof?

Note

+and·should be taken as the usual addition and multiplication onZ.|·|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 fromfwhenw=x=1 andy6=z

7

(ii) This is the same asf

(iii) This is different fromfwhenw=x=1 andy6=z

(iv) This is different fromfwhenw6=xandy6=z

(v) This is different fromfwhenw=x=0 andy6=z

(vi) This is the same asf

Problem12

Consider the following timetabling arrangement given in lectures:

PotionsCharmsHerbologyAstronomyTransfiguration

HarryRonHarryHermioneHermione

RonLunaGeorgeNevilleFred

MalfoyGinnyNevilleSeamusLuna

The school administrator would like to know if it is possible to arrange an exam schedule where3(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 graphG:

•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 size3(or greater). Thus we can solve the problem by

computing the clique number ofG. 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:

–R

1

=¬(P∧H): Harry is in both classes so we can’t hold these exams at the same time

–R

2

=¬(P∧C): Ron is in both classes

–R

3

=¬(C∧T): Luna is in both classes

–R

4

=¬(A∧T): Hermione is in both classes

–R

5

=¬(H∧A): Neville is in both classes

•Consider the following formula indicating at least three exams are held:

R

6

= (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 requirementsR

1

–R

6

are met. Such an assignment would then tell us which exams

could be held so that there are no clashes (R

1

–R

5

) and at least three exams are held (R

6

).

In other words, we want to know if:

φ=R

1

∧R

2

∧R

3

∧R

4

∧R

5

∧R

6

is satisfiable.

Problem13

We would like to pave a 1×nrectangular path with a mix of 1×1 and 1×3 paving stones.

For example, ifsrepresents a 1×1 stone andtrepresents 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.ssstandtsssshould be considered different arrangements)

a LetP(n,k)be the number of different arrangements of paving stones that can pave a 1×npath using

exactlyk1×3 paving stones.

ExpressP(n,k)either:

•in terms of combinatorial functions defined in lectures; or

•recursively (including base cases) in terms ofP(n

′

,k

′

)wheren

′

≤nandk

′

≤k.

b LetP(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 forP(n)and provide, with justification, an asymptotic upper bound.

Solution

(a)Combinatorial functions solution

If we havek1×3 paving stones, and we are paving a 1×npath, then we will haven−3k1×1

stones; and therefore(n−3k) +k=n−2kstones in total. So we want to count the number of

sequences ofn−2k s’s andt’s where we have exactlyk t’s. We can do this by choosing which

of then−2kletters will bet’s and then filling the remainder withs’s. This can be done in

(

n−2k

k

)

ways.

Recursive solution

Consider tiling a 1×npath withk1×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

usingk−1t-stones. This can be done inP(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 inP(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 ifn<3k(the path is not long enough to fitk t-stones)

•P(n, 0) =1 (we only uses-stones).

(b) Using the same idea as the recursive solution above, we have:

•Either the first stone is at-stone, and there areP(n−3)ways to pave the remaining path,

or

•the first stone is ans-stone, and there areP(n−1)ways to pave the remaining path.

Therefore

P(n) =P(n−1) +P(n−3)

10

and for the base cases we haveP(0) =P(1) =P(2) =1.

To find an asymptotic upper bound, we note thatP(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 givesP(n)∈O(2

n

).

Problem14

Let(Ω,P)be a probability space.

Prove or disprove:

(a) For all eventsA,B⊆Ω: IfP(A) =P(A∩B)thenP(B) =P(A∪B)

(b) For all eventsA,B⊆ΩwithP(A),P(B)>0: IfP(A|B)>P(A)thenP(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 ifP(A) =P(A∩B)thenP(A∪B) =P(B) +0.

(b)

Note

Conditional probability not examined in2022T3

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 ifP(A|B)>P(A):

1<

P(A|B)

P(A)

=

P(B|A)

P(B)

SoP(B|A)>P(B).

Problem15

Suppose we rollnfair, six-sided dice.

LetXbe the random variable that indicates the maximum value of all dice.

(a) Form∈[1, 6]what is the probability thatX≤m?

11

(b) In terms ofn, what is the expected value ofX?

Solution

(a) ForXto be at mostm, we need all dice to showmor less. For each die, the probability that it

showsmor less is

m

6

. Assuming, by default, each die is independent, we therefore have:

P(X≤m) = (

m

6

)

n

(b)Xonly 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 calculateP(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