1.  The Euclidean algorithm   nds the greatest common divisor (gcd) of two positive integers n and m (as inputs). Here is the algorithm:

• If m = n then output gcd(n, m) = n and stop.

• Set a = max{n, m} and b = min{n, m}.

• While b  0 do

Apply the division theorem to a and b to   nd integers q , r such that a = qb + r and 0 ≤ r < b.

Set a = b and b = r .

• Output gcd(m, n) = a and stop.

(a)  Consider the four statements below and list in your answer booklet those that are loop invariants of the algorithm. No proof is needed.

(i)  “b < a” .

(ii)  “10 = 8 + 2” .

(iii) a is an even number.

(iv)  “1 = 2” .

(5 marks)

(b)  Consider the statement:

“gcd(n, m) = gcd(a, b)” .

Prove that the statement is a loop invariant.

Solution:

(a) Statements (i), (ii) and (iv) are loop invariants. Statement (iii) is not.

(b) Suppose that gcd(n, m) = gcd(a, b) before an iteration of the while loop.  During the iteration, we have we have a = qb + r, and values a and b change to anew  = b and bnew  = r . So, anew  and bnew  are linear combinations of old a and b, we have that the gcd(a, b) is a common divisor of anew  and bnew .  Since old a and old b are linear combination of anew  and bnew , we again have that the gcd(anew , bn −w ) is a common divisor of a and b.  These imply that gcd(n, m) = gcd(anew , bnew ).

2.  On the set Z consider the following binary relation R:

R = {(a, b)  |  (|a| ≤ 3 and |b| ≤ 3) or (|a| = |b|)},

where |a| and |b| are the absolute values of the integers a and b.

The relation R is an equivalence relation on Z. (You do NOT need to prove this.) Answer the following questions.

(a) Write down equivalence classes of −2, 11 and −15.

(b) Describe the equivalence classes of R.

(c) How many equivalence classes does R have?

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

Solution:

(a) [−2] = {−3, −2, −1, 0, 1, 2, 3}, [11] = {11, −11} and [−15] = {15, −15}.    (b) The equivalence classes are of the form {a, −a} or {−3, −2, −1, 0, 1, 2, 3}.

(c) There are in  nitely many equivalence classes.

3.  A binary string is a   nite sequence of symbols consisting of 0s and 1s.  Examples of binary strings are the empty string, 0, 1, 00, 01, 10, 11, 000 and 100.

For binary strings u and v, we say that u is a substring of v if for some strings x and y we have v = xuy .  For example, 010 is a substring of 110100, and 010 is not a substring of 0011001.

Let A be the set of all binary strings. Consider the following binary relation R on A:

R = {(u, v) | u is a substring of v}.

Prove each of the following statements:

(a)  R is re  exive.

(b)  R is antisymmetric.

(c)  R is transitive.

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

Solution:

(a) For every string u we have u is substring of u. So (u, u) ∈ R.

(b) Assume that u is a substring of v and v is a substring of u. Then we have u = avb and v = a′ ub′  for some strings a, b, a′ , b′ .  Hence u = avb = aa′ ub′ b.  If one of a, a′ , b, b′  is not empty then we have |u| < |aa′ ub′ b|. This is a contradiction. Hence, u = v .

(c) Assume that u is a substring v and v is a substring of w . This implies there are strings a, a′ , b, b′  such that u = avb and v = awb′ . Therefore u = a′ awb′ b. So u is a substring of w .

4.  On the set A = {2, 3, 4, 6, 7, 9, 12, 18} consider the binary relation R.

R = {(i, j) | i divides j}.

This relation is a partial order on A.  (You do NOT need to prove this.)

Answer the following.

(a) Draw a Hasse diagram of this partial order.

(b) List all maximal elements of this partial order.

(c) List all minimal elements of this partial order.

(5 marks) (3 marks) (2 marks)

Solution:

(a) Hasse diagram drawn.

(b) Maximal elements are: 7, 12, and 18.

(c) Minimal elements are: 2, 3, and 7.

5.   (a)  Consider the graph G given below.

A

(i)  Does G have an Euler circuit?

(ii)  Does G have an Euler path?

(iii)  Does G have a Hamilton circuit?

You must justify your answers.

Solution:

G has neither an Euler circuit nor an Euler path: it has more than 2 degrees of odd vertex. Yes, G has a Hamilton circuit: for example, ABCGFEIHDA.

(b)  Is there a simple graph with degree sequence (1,1,3,3,3,4,6,7)?

You must justify your answer.

Solution:

Assume there is such a graph. Then the vertex of degree 7 is adjacent to all other vertices, so in particular it must be adjacent to both vertices of degree 1.  Hence the vertex v of degree 6 cannot be adjacent to either of the two vertices of degree 1.  But this leaves only six vertices (including v itself) to which the vertex v is adjacent.  Since it is assumed that the graph is simple, v cannot be adjacent to itself, and, therefore, there can be only   ve vertices adjacent to v, contradicting the fact that deg(v) = 6. This contradiction shows that there is no simple graph with the given degree sequence.

6.  Consider the deterministic   nite automaton M with states S := {s0 , s1 , s2 , s3 }, start state

s0 , single accepting state s3 , and alphabet  = {a, b, c}.

The following table describes the transition function T : S ×  7→ S .

(a) Draw the transition diagram for M .

Solution:

See page labelled 6a.

(b) Describe the run for input u = abbccc to M . Does M accept u?

Solution:

s0 s0 s3 s3 s0 s2 s3 . Yes.

(c) Describe the run for input w = bcaca to M . Does M accept w?                      (2 marks)

Solution:

s0 s3 s0 s0 s2 s1 . No.

7.   (a) Let A, B , C be sets and suppose that |A| = 9, |B| = 10, |C| = 17, |A ∪ B| = 15, |A ∪ C| = 20, |B ∪ C| = 18, |A ∪ B ∪ C| = 21.

What is |A ∩ B ∩ C|? You must justify your answer.                                       (5 marks)

Solution:

IEP implies that

|A ∪ B ∪ C| = |A| + |B| + |C| − (|A ∩ B| + |A ∩ C| + |B ∩ C|) + |A ∩ B ∩ C|.

IEP also implies that |X ∪ Y | = |X| + |Y | − (|X| ∩ |Y |). Hence |X ∩ Y | = |X| + |Y | − (|X ∪ Y |).

Apply this to deduce that |A ∩ B| = 4, |A ∩ C| = 6, |B ∩ C| = 9.

Deduce that

|A ∩ B ∩ C| = (9 + 10 + 17) − (4 + 6 + 9) − 21 = 4.

(b) How many binary strings of length 8 either start with 1 or end with two 0s?                 You must justify your answer.                                                                           (5 marks) Solution:

Number of binary strings starting with 1 is 27 .  Number of binary strings ending with two 0s is 26 . Number starting with 1 and ending with two 0s is 25 .

By IEP total is 27 + 26 − 25  = 160.

8.   (a) Let S be a set with 20 elements. Count the number of subsets of S containing more than 2 elements. You must justify your answer.

Solution:

Total number of subsets is 220 .  Subtract the number of subsets containing 0 or 1 or 2 elements. Total is 220 − (1 + 20 + 10 × 19).

(b) How many integral solutions are there to the equation

x1 + x2 + x3 + x4  = 12

if x1 , x2 , x3 , x4  ≥ 0 and x4  ≤ 2? You must justify your answer.                        (5 marks)

Solution:

If all xi  ≥ 0 then the number of solutions is  .  Subtract from this quantity the number of solutions where x4  ≥ 3. Total is   −  3(12)  = 235.

9.   (a) Prove that a simple bipartite graph on v vertices has at most v2 /4 edges.        (4 marks)

Solution:

Let the number of vertices be v . Let |V1 | = k, hence |V2 | = v − k for some k > 0. The number of edges is ≤ k(v − k) which is maximised when k = v/2 (for v even), giving v2 /4 edges.

(b)  Show that K3,3  achieves the bound given in (a).                                               (2 marks)

Solution:

6 vertices and precisely v2 /4 = 9 edges.

(c) Let G be the graph C6 . What is the degree sequence of G? Draw a simple graph

which has the same degree sequence as G but which is not isomorphic to G.        (4 marks)

Solution:

C6  has 6 vertices of degree 2, and no other vertices, so it has degree sequence (0, 0, 6). One non-isomorphic graph with the same degree sequence is