## 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