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?
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
answers, then we will give you marks only for ”your worst answer”, as this
indicates how well you understood the question.
• Some of the questions are very easy (with the help of the lecture notes or
book). You can use the material presented in the lecture or book (without
proving it). You do not need to write more than necessary (see comment
above).
• When giving answers to questions, we always would like you to prove/explain/motivate your answers.
• If you use further resources (books, scientific papers, the internet,…) to
formulate your answers, then add references to your sources.
4