1.  Solve the following recurrence relation:

You must show your detailed working.

2. Prove that AxAy(3zP (x, y, z) → AzP (x, y, z)) is not a tautology.

3. Define f : N ,_→ N x N by f (x) = (x, x + 2). Decide whether or not f is one-to-one, onto, invertible. You must justify your answers.

4.  (a) Decide if there exists a simple graph on n vertices where each vertex has degree n. You must justify your answer.

(b) Decide whether or not there is a simple graph with degree sequence

[0, 1, 1, 1, 1, 2]. You must justify your answer.

5.  (a) Prove that every connected graph with 3 vertices has an Euler circuit or walk.

(b) Determine the smallest positive value of n for which a simple graph on n vertices

and 2n edges can exist. Give an example of such a graph for the smallest n. 

6.  (a) Define a relation R on z as follows: aRb if and only if every prime factor of a is a prime factor of b. Decide whether or not R is a partial order on z.

You must justify your answer.                       

(b) Let b, c e z and r is a positive integer. Prove that if b = c mod r,

then b2  = c2  mod r .                                  

7.  Suppose we want to design a prefix code to encode the text ABRACADABRA.

(a) Use Huffman’s algorithm to construct an optimal binary tree for this text.

To obtain full marks, you must show the intermediate steps of the construction, not simply the final tree.

(b)  Compute its total weight.

(c) Write the string consisting of 0s and 1s that encodes the given text.

8. Let A = {0, . . . , 9} and let B = {x e A I x%5 e {0, 3}}.

(a) How many 8-letter strings over A begin and end with an element of B?

You must justify your answer.

(b) How many 8-letter strings over A either begin with an element of B ,

or end with an element of B, or both? You must justify your answer.

(c)  Consider a 8-letter string over A whose first letter is not in B and its last letter is not in B . How many strings of this kind are there? You must justify your answer.

9. Let A be a fixed 8-element subset of {10, . . . , 24}. Prove that A has two different 4-element subsets B and C so that the sum of the elements of B equals the sum of the elements of C .