Instructions: • The exam consists of 10 questions for a total of 200 marks • Solutions should be submitted as a pdf, maximum size 20Mb. • Solutions should be submitted via give/webCMS. Multiple submissions are al￾lowed, your last submission before the due date will be the submission marked. • Deadline for submissions is 10am, Tuesday 8 December 2020 (AEDST). • Late submissions will be penalized at 25% (applied to raw mark) per 15 minutes or part thereof. • Existing written materials (i.e. passive resources) may be used, but should be properly referenced. Obtaining, or trying to obtain solutions from active re￾sources (e.g. social media, forums, other people) is a breach of the University’s Plagiarism Policy and will be subject to disciplinary action as outlined in the Student Code of Conduct. • Unless explicitly stated, you should prove/explain/motivate your answers. You are being assessed on your understanding and ability. • Be careful with giving multiple or alternative answers. If you give multiple an￾swers, then we will give you marks only for your worst answer, as this indicates how well you understood the question. • Number of pages in this exam paper: 8, including this cover page. Question 1 (20 marks) (a) Using only the functions | · |, b·c, d·e, div, %, basic arithmetic functions (+, ×, , and ÷), and numeric constants, define the following functions: (i) f : R \ {0} → {−1, 1} given by f(x) =  1 if x < 0 1 if x > 0 (2 marks) (ii) g : R → {0, 1} given by g(x) =  1 if x ∈ Z 0 if x ∈/ Z (2 marks) (iii) h : N → {0, 1} given by h(x) =  1 if 5|x 0 if 5 - x (2 marks) (iv) min : R × R → R given by min(x, y) =  x if x ≤ y y if y < x (2 marks) (v) q : R → {0, 1} given by q(x) =  1 if x ∈ Z and 5|x 0 otherwise (2 marks) (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 n0 = a 5b. • Repeat with n0 in place of n. So, for example, if n = 12345, then n0 = 1234 5 · 5 = 1209. Repeating would create 120 5 · 9 = 75; 7 5 · 5 = 18; and so on. (i) Prove that 17|n if and only if 17|n0. (6 marks) This shows that we can repeat the process with n0 , 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 n0 is reached. (4 marks) 1 Question 2 (20 marks) (a) Prove, or provide a counterexample to disprove, the following for all sets A, B: (i) If there is a set X such that A ∩ X = B ∩ X then A = B. (4 marks) (ii) If there is a set X such that A ⊕ X = B ⊕ X then A = B. (4 marks) (iii) If there is a set X such that A ∩ X = B ∩ X and A ∪ X = B ∪ X then A = B. (4 marks) (b) Let Σ be a finite set. Prove, or provide a counterexample to disprove, the following for all languages X,Y, Z ⊆ Σ∗: (i) If XY = YZ then X∗Y = YZ∗. (4 marks) (ii) If X∗Y = YZ∗ then XY = YZ. (4 marks) Question 3 (20 marks) Let (A, ) be a poset. Define f : A → Pow(A) as follows: f(a) = {x : x ≤ a}. (a) Prove that a  b if, and only if, f(a) ⊆ f(b). (6 marks) (b) Prove that f is injective. (4 marks) (c) Prove that f is not surjective. (4 marks) (d) Prove that if c = glb(a, b) exists, then f(c) = f(a) ∩ f(b). (6 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 ◦ g = f ◦ h implies g = h (8 marks) 2 (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) (3 log 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 v0 be a vertex such that (v0, v) ∈ E Let v = v0 end while Let G0 be the graph that results from removing v and all incident edges Let L = topSort(G0) 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) 3 Question 6 (20 marks) Recall from Assignment 2 the recursive definition of a binary tree: • (B): An empty tree τ • (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 τ 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(τ) = 0 • count((Tleft, Tright)) = 1 + count(Tleft) + count(Tright) (c) Let P(T) be the proposition that: count(T) ≤ 2 height(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 height(T) 2 1. Prove that Q(T) holds for all binary trees T. (6 marks) 4 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 = x0. (4 marks) (ii) For all x, y, z: ((x ∧ y) ∨ (x0 ∧ z)) ∨ (y ∧ z) = (x ∧ y) ∨ (x0 ∧ 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) 5 (d) The following graph: • • • • • • • • • • contains a subdivision of K4. (4 marks) (e) K2,16 contains a subdivision of K4,4. (4 marks) Question 9 (20 marks) For n ∈ 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(n0) where n0 < 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(n0, k0) where n0 < n and k0 ≤ k. Remember to include a base case. (4 marks) Hint: Each f ∈ AAn k can be viewed as f = g ∪ {(n, y)} where y ∈ Ak and g is a function with domain An 1. (e) Let E(n, k) denote the number of equivalence relations on An that have exactly k equivalence classes. With justification, define E(n, k) in terms of F(n, k). (4 marks) 6 Question 10 (20 marks) Prove, or provide a counterexample to disprove the following for all discrete probability distributions P, all events A and B, and all random variables X and Y: (a) P(A \ B) ≥ P(A) P(B) (6 marks) (b) If 0 < P(A) ≤ P(B) then P(A|B) ≤ P(B|A) (6 marks) (c) P(X > E(X)) ≥ 12 (4 marks) (d) If E(X) > E(Y) then P(X > Y) > 0 (4 marks)