Description
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
house over the road?
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
• add(m, n + 1) = add(m, n) + 1.
We will now show that add is commutative!
(a) Let P(n) be the proposition
P(n) : add(n, 0) = add(0, n).
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?
