Question 1               (20 marks)

(a) Using only the functions I . I, |.|,「.1, div, %, basic arithmetic functions (+, ×, _, and ÷), and numeric constants, define the following functions:

(i) f : R \ {0} → {_1, 1} given by f (x) = {1(_)1

(iv) min : R × R → R given by min(x, y) = {y(x)

(v) q : R → {0, 1} given by q(x) = { 0(1)

(b) The following process leads to a rule for determining if a large number n is

divisible by 17:

● Remove the last digit, b, of n leaving a smaller number a.

● Let n/ = a _ 5b.

● Repeat with n/ in place of n.

So, for example, if n = 12345, then n/  = 1234 _ 5 . 5 = 1209.  Repeating would create 120 _ 5 . 9 = 75; 7 _ 5 . 5 = _18; and so on.

(i) Prove that 17In if and only if 17In/ .                                                     (6 marks)

This shows that we can repeat the process with n/, and so on, until we reach a “small enough” value that checking divisibility by 17 is straightforward.

(ii) Give, with justification, an asymptotic upper bound in terms of n, for the number of times this process needs to be repeated before a negative n/  is reached.                                                                                                  (4 marks)

Question 4               (20 marks)

(a) Prove that for all sets A, B, C there is a bijection between (A × B) × C and A ×

(B × C).                                                                                                          (4 marks)

(b) Prove that f : S → T is injective if, and only if, for all functions g, h : U → S: f o g = f o h   implies   g = h (8 marks)

(c) Order the following functions in increasing order of asymptotic complexity:

(I) n3 ^n

(II) n3 log(n)

(III) T(n) where T(0) = 1 and T(n) = T(n _ 3) + n3

(IV) T(n) where T(0) = 1 and T(n) = 6T(n/2) + n3

(V)  (3log n )2

(VI) 3(log n)2

Justify your ordering.

(8 marks)

Question 5                    (20 marks)

Consider the following code snippet, which takes an acyclic directed graph (which does not contain loops) and returns a topological ordering of the vertices (i.e. vertex order respects edge direction):

topSort(G):

If G has no vertices :

return an empty list

endif

Let v be any vertex of G

while v has in-degree > 0:

Let v\ be a vertex such that (v\, v) e E

Let v = v\

end while

Let G\ be the graph that results from removing v and all incident edges Let L = topSort(G\ )

prepend L with v

return L

For this question you may assume that removing a vertex and all incident edges; or prepending a vertex to a list, can be executed in O(1) time. Assume that accessing a single matrix entry can be executed in O(1) time, but searching a row (column) of an n × m matrix will take O(m) time (O(n) time, respectively).

Calculate the asymptotic running time of the above code snippet in terms of n: the number of vertices of G, and m: the number of edges of G:

(a) When G is given as an n × n adjacency matrix. (6 marks)

(b) When G is given as an adjacency list. (6 marks)

(c) When G is given as an n × m incidence matrix. (8 marks)

Question 6                                                                                                  (20 marks)

Recall from Assignment 2 the recursive definition of a binary tree:

.  (B): An empty tree T

.  (R): An ordered pair of binary trees (Tleft, Tright)

The height of a binary tree is defined to be the length of the longest path from the root node (node with no predecessors) to a leaf. For convenience, we define the height of T to be _1. The example tree in Assignment 2 has height 2.

(a) Based on the recursive definition above, recursively define a function height(T)

that computes the height of a binary tree T.                                               (4 marks)

A binary tree is balanced if it is the empty tree, or if the heights of its two subtrees Tleft  and Tright  differ by at most 1.  A binary tree is fully-balanced if every subtree is balanced. The example tree in Assignment 2 is fully-balanced.

(b) Based on part (a) and the recursive definition above, recursively define a function balanced(T) that returns an element of B indicating whether or not the binary tree

T is fully-balanced.                                                                                        (4 marks)

Recall from Assignment 2 the count function that counts the number of nodes in a binary tree:

. count(T) = 0

. count((Tleft, Tright)) = 1 + count(Tleft) + count(Tright)

(c) Let P(T) be the proposition that:

count(T) < 2height(T)+1 _ 1.

Prove that P(T) holds for all binary trees T.                                               (6 marks)

(d) Let Q(T) be the proposition that:

If balanced(T) then    count(T) > 2 _ 1.

Prove that Q(T) holds for all binary trees T.                                               (6 marks)

Question 7              (20 marks)

(a) You are on a spaceship filled with crewmates and imposters.   Imposters will always lie, and crewmates will always tell the truth. The following statements are made:

. Red says: Either myself and Blue are both crew, or we are both imposters. . Orange says: At least one of Red and Green is an imposter.

. Green says: Red is an imposter.

. Blue says: Red is an imposter.

(i) Formulate this as a problem in propositional logic, defining the proposi- tional variables and what they represent;  any formulas that are relevant; and the logical problem you are solving.                                            (6 marks)

(ii) Use your answer from (i) to determine what possible combinations of crew- mate/imposters there are that are consistent with this system.          (6 marks)

(b) Prove, or provide a counterexample to disprove the following hold in all Boolean

Algebras:

(i) There is no x such that x = x\ .                                                             (4 marks)

(ii) For all x, y, z: ((x V y) v (x\ V z)) v (y V z) = (x V y) v (x\ V z).        (4 marks)

Question 8                                                                                                  (20 marks)

Prove or disprove:

(a) The degree sequence of a graph provides enough information to determine if it

has an Eulerian cycle.                                                                                    (4 marks)

(b) If a graph G has an even number of vertices and an Eulerian cycle, then it has an even number of edges.       (4 marks)

(c) If a graph G has an even number of vertices and an Eulerian cycle, then it has chromatic number at most 2.        (4 marks)

(d) The following graph:

.

.

.                                           .

. .

.             .

. .

contains a subdivision of K4 .

(e) K2,16 contains a subdivision of K4,4 .

Question 9                                                                                                  (20 marks)

For n e N with n > 0 let An  = {1, 2, . . . , n}. Let E(n) denote the number of equiva- lence relations there are on An, and let F(n, k) denote the number of surjective func- tions there are from An to Ak .

(a) With justification, give a simple formula (using combinatorial functions defined

in lectures) for F(n, n).                                                                                  (4 marks)

(b) With justification, give a simple formula (using combinatorial functions defined

in lectures) for F(n, 2).                                                                                   (4 marks)

(c) With justification, give a recurrence equation for E(n) involving (one or more) E(n\ ) where n\  < n. Remember to include a base case. (4 marks) Hint: How many equivalence relations are there on An where the equivalence class of n has exactly i elements?

(d) With justification, give a recurrence equation for F(n, k) involving (one or more) F(n\, k\ ) where n\  < n and k\ < k. Remember to include a base case.