Question 1                 (20 marks)

(a) Prove, or give a counterexample to disprove:

(i) For all x e R:

I「x|I =「IxI|

(4 marks)

(ii) For all x e Z:

42Ix7 _ x

(4 marks)

(iii) For all x, y, z e Z, with z > 1 and z | y:

(x div y) = ((x % z) div (y % z))    (mod z)

(4 marks)

(b) The following code snippet could be used to find the smallest i such that i > n2 and kIi:

myFunction(n ,k):

i = 0

while i < n2  :

j = 0

while j < k :

i = i + 1

j = j + 1

end while

end while

return i

(i) Assuming k is a constant that is not dependent on n, provide an asymptotic upper bound, in terms of n, for the running time of this algorithm. Partial marks may be awarded for correct, but sub-optimal bounds.           (4 marks)

(ii) Assuming the number-theoretic functions covered in this course (I . I,「.|, 「.1, div, %), and the standard arithmetic operations, can be computed in O(1) time, find a constant-time replacement for the above code.     (4 marks)

Question 2              (20 marks)

(a) Prove, or give a counterexample to disprove for all sets A, B, C, D:

(i)  (A · B) = (B · A)                                                                             (4 marks)

(ii) A u (B · C) = (A · B) u (A · C)                                                     (4 marks)

(iii)  (A × B) n (C × D) = (A n C) × (B n D)                                           (4 marks)

(b)     (i) The Laws of Set Operations only define equality between sets. How can they

be used to show, say, A C B?

(ii) Use the Laws of Set Operations to show              (2 marks)

A · B C A u B.

Partial marks are available for a proof that does not use the Laws of Set Operations.                                                                                            (6 marks)

Question 3           (20 marks)

Let (B, 3) be a partially ordered set, A be a set, and f : A → B a function from A to

B. Define R C A × A as follows:

(a, b) e R    if and only if    f (a) 3 f (b)

(a) Give a counterexample to show that in general R is not a partial order.  (4 marks)

(b)     (i) State a restriction on f that will ensure R is a partial order, and

(ii) Prove that under that restriction R is a partial order.

(c) Prove that R n R- is an equivalence relation.

(1 mark) (9 marks)

(6 marks)

Question 4

Let z = {a, b} and define f : z* → R recursively as follows:

● f (入) = 0,

● f (aw) =  + f (w) for w e z*, and

● f (bw) = _  + f (w) for w e z* .

(a) What is f (abba)?

(b) Prove that f (w) e (_1, 1) for all w e z*

(c) Prove, or give a counterexample to disprove:

(i) f is injective      (ii)  Im(f ) = ( _1, 1)

(20 marks)

(2 marks) (6 marks)

(6 marks) (6 marks)

Question 5                                                                                                  (20 marks) Consider the following code snippet that defines a function that works on a set A:

myFunction(A):

if IAI < 1:

print(’*’)

else:

(A1, A2) = split(A)

myFunction(A1)

myFunction(A2)

end if

Here split(X) is a program that runs in O(IXI) time and partitions the set X into two non-empty sets X1 and X2 .

Give, with justification, asymptotic upper bounds, in terms of n = IAI, for the run- ning time of myFunction(A) when:

(a) split(X) always partitions X into equal sized sets.1

(b) split(X) can partition X into non-empty sets of any size.

(c) split(X) always partitions X into non-empty sets of size at least  .

Partial marks may be awarded for correct, but sub-optimal bounds.

(6 marks) (6 marks) (8 marks)

Question 8              (20 marks)

You are taking an exam that has 6 easy questions and 4 difficult questions. Assuming all questions are distinguishable, how many ways are there of ordering the questions so that:

(a) All the easy questions come first.                                                                 (4 marks)

(b) Each pair of difficult questions is separated by at least 2 easy questions. (4 marks) (c) Each pair of difficult questions is separated by at least 1 easy question.  (4 marks) (d) Each pair of difficult questions is separated by at most 1 easy question.  (4 marks)

(e) Each pair of difficult questions is separated by exactly 1 easy question.  (4 marks)

Question 9

Suppose two players, A and B, are playing the following game:

. A starts.

. The players take turns rolling a 6-sided die.

. Whoever rolls the first 6 wins the game.

(a) What is the probability that A wins?

(20 marks)

(6 marks)

(b) What is the expected number of die rolls before a winner is determined?(2 marks)

Now suppose we consider the following addition to the rules:

. If a player rolls a number that has already been seen then they roll again until an unseen number is rolled.

(c) What is the probability that A wins this game?                                          (4 marks)

(d) If we say a turn ends when an unseen number is rolled, what is the expected number of turns before a winner is determined?                                        (4 marks)

(e) At the start of B’s second turn, what is the expected number of die rolls before a winner is determined?                                                                                   (4 marks)

Question 10        (20 marks)