Problem 1 (12 marks)

Consider the following two algorithms that naïvely compute the sum and product of two n * n matrices.

sum(A ,B):

for i e [0, n):

for j e [0, n):

C[i, j] = A[i, j] + B[i, j]

end for

end for

return C

product(A ,B):

for i e [0, n):

for j e [0, n):

C[i, j] = add{A[i, k] · B[k, j] : k e [0, n)}

end for

end for

return C

Assuming that adding and multiplying matrix elements can be carried out in O(1) time, and add will add the elements of a set S in O(ISI) time:

(a) Give an asymptotic upper bound, in terms of n, for the running time of sum.      (b) Give an asymptotic upper bound, in terms of n, for the running time of product.

(3 marks) (3 marks)

When n is even, we can define a recursive procedure for multiplying two n * n matrices as follows. First, break the matrices into smaller submatrices:

A = ╱  U(S)    V(T)  、        B = ╱  Y(W)    Z(X)  、

where S, T, U, V, W, X, Y, Z are  *  matrices. Then it is possible to show:

AB =   、

where SW + TY, SX + TZ, etc.  are sums of products of the smaller matrices.  If n is a power of 2, each smaller product (SW, TY, etc) can be computed recursively, until the product of 1 * 1 matrices needs to be computed – which is nothing more than a simple multiplication, taking O(1) time.

Assume n is a power of 2, and let T(n) be the worst-case running time for computing the product of two n * n matrices using this method.

(c) With justification, give a recurrence equation for T(n).

(d) Find an asymptotic upper bound for T(n).

(4 marks) (2 marks)

Problem 2

Recall from Assignment 2 the neighbourhood of eight houses:

(18 marks)

As before, 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. Again we would like to solve the problem of finding the minimum number of channels needed, but this time we will solve it using techniques from logic and from probability. Rather than directly asking for the minimum number of channels required, we ask if it is possible to solve it with just 2 channels. So suppose each wi-fi network can either be on channel hi or on channel lo. Is it possible to assign channels to networks so that there is no interference?

(a) Formulate this problem as a problem in propositional logic. Specifically:

(i) Define your propositional variables                                                                                      (4 marks)

(ii) Define any propositional formulas that are appropriate and indicate what propositions they

represent.                                                                                                                                 (4 marks)

(iii) Indicate how you would solve the problem (or show that it cannot be done) using propositional

logic. It is sufficient to explain the method, you do not need to provide a solution.        (2 marks)

(iv)· Explain how to modify your answer(s) to (i) and (ii) if the goal was to see if it is possible to solve

with 3 channels rather than 2.                                                                                                (4 marks)

(b) Suppose each house chooses, uniformly at random, one of the two network channels.  What is the probability that there will be no interference?                                                                              (4 marks)

Problem 3

Prove the following results hold in all Boolean Algebras:

(a) For all x: (x V 1\) v (x\ V 1) = x\

(b) For all x, y: (x V y) v x = x

(c) For all x, y: y\ V ((x v y) V x\) = 0

(12 marks)

(4 marks) (4 marks) (4 marks)

Problem 5

Prove or disprove the following logical equivalences:

(a)  -(p → q) = (-p → -q)

(b)  ((p V q) → r) = (p → (q → r))

(c)  ((p v (q v r)) V (r v p)) = ((p V q) v (r v p))

(12 marks)

(4 marks) (4 marks)

(4 marks)

Problem 6                                                                                                                                              (16 marks)

Recall from Assignment 2 the definition of a binary tree data structure: either an empty tree, or a node with two children that are trees.

Let T(n) denote the number of binary trees with n nodes.  For example T(3) = 5 because there are five binary trees with three nodes:

(a) Using the recursive definition of a binary tree structure, or otherwise, derive a recurrence equation for

T(n).                                                                                                                                                  (6 marks)

A full binary tree is a non-empty binary tree where every node has either two non-empty children (i.e. is a fully-internal node) or two empty children (i.e. is a leaf).

(b) Using observations from Assignment 2, or otherwise, explain why a full binary tree must have an odd

number of nodes.                                                                                                                             (2 marks)

(c) Let B(n) denote the number of full binary trees with n nodes. Derive an expression for B(n), involving T(n\) where n\  < n. Hint: Relate the internal nodes of a full binary tree to T(n).                            (4 marks)

A well-formed formula is in Negated normal form if it consists of just V, v, and literals (i.e. propositional variables or negations of propositional variables). For example, (p v (-q V -r)) is in negated normal form; but (p v -(q v r)) is not.

Let F(n) denote the number of well-formed, negated normal form formulas1 there are that use precisely n propositional variables exactly one time each. So F(1) = 2, F(2) = 16, and F(4) = 15360.

(d) Using your answer for part (c), give an expression for F(n).                                                       (4 marks)

(16 marks)

and consider the following process:

● Initially, start at 1.

● At each time step, choose one of the outgoing edges from your current location uniformly at random, and follow it to the next location. For example, if your current location was 2, then with probability  you would move to 3; with probability  you would move to 4; with probability  you would move to 5; and with probability  you would stay at 2.

Let p1 (n), p2 (n), p3 (n), p4 (n), p5 (n) be the probability your location after n time steps is 1, 2, 3, 4, or 5 respectively. So p1 (0) = 1 and p2 (0) = p3 (0) = p4 (0) = p5 (0) = 0.

(a) Express p1 (n + 1), p2 (n + 1), p3 (n + 1), p4 (n + 1), and p5 (n + 1) in terms of p1 (n), p2 (n), p3 (n), p4 (n),

and p5 (n).                                                                                                                                         (5 marks)

(b) Prove ONE of the following:

(i) For all n e N: p1 (n) = 2n(1)

(ii) For all n e N: p2 (n) = 2 ╱ 2n(1)   × 4n(1) 、

(iii) For all n e N: p3 (n) = p4 (n) = (n × 2)2n(1)  +4n(2)

(iv) For all n e N: p5 (n) = 1 × (2n × 1)2n(1)   × 4n(2)

(5 marks) (6 marks) (7 marks) (8 marks)

(c) For each n e N let Xn be the random variable that has value:

● 0 if your location at time n is 1;

●  1 if your location at time n is 2;

● 2 if your location at time n is 3 or 4; and

● 3 if your location at time n is 5

(i. e. Xn is the length of the longest path from 1 to your location at time n).

What is the expected value of X3?

Problem 8                                                                                                                                              (1o marks)

In this question we are going to look at modelling the spread of a virus in a network (or news in a social network).

Consider the following graph:

and consider the following process:

● Initially, at time n = 0, A is infected and no other vertices are infected.

● At each time step, each infected vertex does the following:

– for each uninfected neighbour, spread the infection to that vertex with probability  .

So if A and B were infected and C and D were not, then in one time step, the virus would spread to both C and D with probability ; spread to C only with probability ; spread to D only with probability ; and not spread any further with probability  .

Let pA (n), pB (n), pC (n), pD (n) be the probability that A, B, C, D (respectively) are infected after n time steps. So pA (0) = 1 and pB (0) = pC (0) = pD (0) = 0.

(a) Express pD (n + 1) in terms of pA (n), pB (n), pC (n) and pD (n).                                                  (4 marks)

(b) Find an expression for pD (n) in terms of n only. You do not need to prove the result, but you should

briefly justify your answer. Hint: Try to relate this system with Question 7                                    (4 marks)

(c)* What is the expected number of infected vertices after n = 3 time steps?                                 (2 marks)