Sale!

# COMP 9020 Assignment 2 solved

Original price was: \$30.00.Current price is: \$25.00.

Category:

## Description

5/5 - (1 vote)

1. Eight houses are lined up on a street, with four on each side of the road
as shown:
Each house wants to set up its own wi-fi network, but the wireless networks
of neighbouring houses – that is, houses that are either next to each other
(ignoring trees) or over the road from one another (directly opposite) –
can interfere, and must therefore be on different channels.

Houses that are
sufficiently far away may use the same wi-fi channel. Your goal is to find
the minimum number of different channels the neighbourhood requires.
(a) Explain how this can be formulated as a graph-based problem.
(b) What is the minimum number of wi-fi channels required for the neighbourhood?
(c) How does your answer to (b) change if a house’s wireless network
can also interfere with those of the houses to the left and right of the

2. In the lectures it was mentioned that determining if a graph can be threecoloured is a “difficult problem”. It was also mentioned that determining
if a formula in CNF was satisfiable is a “difficult problem”. We will now
show the two problems are related, relatively simply, by reducing the threecolourability problem to the satisfiability problem. That is, given a graph,
G, we will define a formula (in CNF) ϕG such that G is three-colourable
if, and only if ϕG is satisfiable.

Let G = (V, E) be a graph, and C = {red, green, blue} be a set of three
colours. Define Prop := {Pv,c : v ∈ V and c ∈ C}. Intuitively, Pv,c
represents the proposition “vertex v has colour c”. Recall that a literal is
either p or ¬p where p ∈ Prop.
(a) Define the proposition Av: “vertex v has at least one colour” using
a disjunction of literals.
(b) Define the proposition Bv: “vertex v has at most one colour” in CNF.
1
(c) Define the proposition Cu,v: “vertex u and vertex v have different
colours” in CNF.

(d) Define ϕG. You may wish to use the notation Vk
i=0 ψi
, which is
shorthand for ψ0 ∧ ψ1 ∧ . . . ∧ ψk, though the variations V
v∈V
and
V
{u,v}∈E will likely be more useful.
3. Let (A, ∨, ∧,
0
, 0, 1) be a Boolean algebra. Define a relation v on A as
follows:

x v y if x ∨ y = y.
(a) Show that v is a partial order (using the laws of Boolean algebra).
(b) In the Boolean algebra defined by the subsets of a set X, what partial
order does v correspond to?
(c) While v is not very interesting in the two-valued logic associated
with Propositional Logic, the “propositional analogue” would be the
Boolean function:

(x ∨ y) ↔ y.
What Boolean connective is (x ∨ y) ↔ y logically equivalent to?
4. We can define addition1 over natural numbers inductively as follows:
• add(m, 0) = m, and
We will now show that add is commutative!
(a) Let P(n) be the proposition
Prove that P(n) holds for all n ∈ N.

(b) Let Q(n) be the proposition
Q(n) : If a + b = n and a, b > 0 then add(a, b) = add(b, a).
Prove that Q(n) holds for all n ∈ N. (Hint: It may be easier to show
that P(n) ∧ Q(n) holds for all n).
5. Define the sequence, an, recursively as:
a0 = 0 a1 = 1 an = 5an−1 − 6an−2.
1Note: the “+1” in “n+1” should be considered a structural concept, and not (immediately) related to the function we are defining
2

Consider the following algorithms for computing an:
rec a(n) : iter a(n) :
if n < 2 : return n if n < 2 : return n
else : else :
x := rec a(n − 1) x := 1
y := rec a(n − 2) y := 0
return 5x − 6y i := 1
while i < n :
t := x
x := 5x − 6y
y := t
i := i + 1
return x
(a) Give asymptotic upper bounds for the running times for rec a and
iter a to compute an.

(b) By considering an + 2n, guess an expression for an. Prove your guess
is correct for all n ∈ N.
(c) Can you find a more efficient (i.e. asymptotically faster) method for
computing an?
3

### Advice on how to do the assignment

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 pdf
• Be careful with giving multiple or alternative answers. If you give multiple