Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP9020 Assignment
Objectives and Outcomes The purpose of this assignment is to build your mathematical maturity in the areas of Equivalence Relations, Functions, Graph Theory, Recursion and Induction. Most questions are presented at a highly abstract level so that the consequences are very general, and can be applied in a variety of situations: not just later on in the course, but also beyond. The specific motivation for each problem can be summarised as follows: Problem 1: This question shows another, very useful, characterization of equivalence relations, connecting them with functions. This goes along with the characterization in terms of partitions (i.e. a connection with sets) described in lectures. Most of the examples of equivalence relations given in lectures and quizzes (e.g. Quiz 4, M1) fit this characterization; and we use the result again in Problem 2. Problem 2: This question shows that, in certain circumstances, it is possible to “extend” addition and multi- plication to equivalence classes. A variation of this result (for a different equivalence relation) establishes the facts about how addtion and multiplication interact with =n stated in lectures. This particular re- sult shows a connection between the matrix representation of relations and the adjacency matrix of their graphical representation (the former corresponding to a matrix of equivalence classes). We will see the semiring E again when we cover Boolean Logic. Problem 3: The aim of this question is to model a concrete (“real-world”) problem abstractly using Graph Theory. An abstract model lets us: identify the important aspects of a problem and ignore the extra- neous; identify connections with other, seemingly unrelated problems; and make use of other, more general, tools and results to solve the specific problem. We will revisit this problem in Assignment 3, where we will model it with Propositional Logic. Problem 4: The aim of this question is to show how you can prove and disprove whether or not a graph has a particular graph property (in this case, planarity). While the specific technique of finding/excluding subdivisions is not necessarily applicable to other graph properties, the process illustrates the general principle of how you might prove a “negative” property. Problem 5: The similarity between relational composition (;) and transitivity was remarked upon in lectures. This problem clarifies that connection, showing how relational composition can be used to recursively “add” transitivity to a non-transitive relation. This question ties together several topics: Relations, Recursion, Induction (and, obliquely, Formal Languages), as well as results from the first Assignment; and reinforces the basic concepts of those topics. Problem 6: The binary tree data structure is commonly taught in introductory Computer Science and should be familiar to most students taking COMP9020 (though it is not essential to know about them for the purposes of this question). In this question we take an abstract model of a binary tree and use this to create abstract, recursive “programs” (recursively defined functions) and then reason about these programs. We will revisit this question in Assignment 3 when we use binary trees themselves as abstract models (of logical formulas) and utilise the recursive definition to count these objects. Problem 7: In Problems 5 and 6, the necessary recursive definition has been provided. The aim of this ques- tion is to create your own recursive definition, providing a formal definition of the previously informally defined lexicographic order. This provides a connection between recursion and partial orders, further highlighting the ubiquity of recursion in many parts of Computer Science. After completing this assignment, you will: • Be able to make logical arguments about abstract concepts [Problems 1, 2, 4, 5 and 7] • Be able to create and reason about abstract models of concrete (“real-world”) problems and objects [Problems 3, 6 and 7] • Understand several deeper connections between different topics of the course [Problems 1, 2, 5 and 7] 1 Due: Monday, 31st October, 12:00 (AEDST) Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose should be typed, not handwritten. Use of LATEX is encouraged, but not required. Discussion of assignment material with others is permitted, but the work submitted must be your own in line with the University’s plagiarism policy. Problem 1 (12 marks) Let S be a set. (a) Show that for any set T and any function f : S! T, the relation Rf ✓ S⇥ S, defined as: (s, s0) 2 Rf if and only if f (s) = f (s0) is an equivalence relation. 6 marks (b) Show that if R ✓ S⇥ S is an equivalence relation, then there exists a set T and a function fR : S ! T such that: (s, s0) 2 R if and only if fR(s) = fR(s0) 6 marks Problem 2 (20 marks) Let B = {0, 1} and consider the function f : N ! B given by f (n) = ⇢ 1 if n > 0, 0 otherwise. (a) Show that for all a, b 2 N: (i) f (a+ b) = max{ f (a), f (b)} 3 marks (ii) f (ab) = min{ f (a), f (b)} 3 marks From Problem 1, we know that Rf ✓ N⇥N, the relation given by: (m, n) 2 Rf if and only if f (m) = f (n) is an equivalence relation. Let E ✓ Pow(N) be the set of equivalence classes of Rf , and for n 2 N, let [n] 2 E denote the equivalence class of n. We would like to define binary operations, and , on E as follows: [x] [y] := [x+ y] [x] [y] := [xy]. 2 The difficulty is that the operands [x] and [y] can have multiple representations (e.g. if z 2 [x] then [x] = [z]), and so it is not clear that such a definition makes sense: if we take a different representation of the operands, do we still end up with the same result? For example, suppose [1] = [2]. Then we would want [1] [1] = [2] [2], but with the proposed definition above, we would have [1] [1] = [2], and [2] [2] = [4], and it is by no means clear that [2] = [4]. Our next step is to show that such a definition makes sense. (b) Define relations , ✓ E2 ⇥E as follows: ((X,Y),Z) 2 if and only if there is x, y 2 N such that X = [x], Y = [y] and Z = [x+ y] ((X,Y),Z) 2 if and only if there is x, y 2 N such that X = [x], Y = [y] and Z = [xy] (i) Show that is a function. 3 marks (ii) Show that is a function. 3 marks Part (b) shows that the informal definition of and given earlier is well-defined, so from now we will view and as binary operations on E, that is , : E⇥E ! E. (c) Show that for all A, B,C 2 E: (i) A [1] = A 3 marks (ii) A B = B A 3 marks (iii) A (B C) = (A B) (A C) 2 marks Remark Objects that have a concept of “addition” () and “multiplication” () where: • addition and multiplication are associative, • both operations have identities (see (c)(i)), • addition is commutative (see (c)(ii)), and • multiplication distributes over addition (see (c)(iii)) are known as semirings. We have already seen a number of semirings in this course: • The natural numbers with usual addition and multiplication, • Integers modulo n with addition and multiplication modulo n, • Subsets of a set X with union and intersection, • Languages with union and concatenation, • Binary relations with union and relational composition (see Assignment 1), • Matrices with matrix addition and matrix multiplication. 3 Problem 3 (12 marks) Eight houses are lined up on a street, with four on each side of the road as shown: Each house wants to set up its own wi-fi network, but the wireless networks of neighbouring houses – that is, houses that are either next to each other (ignoring trees) or over the road from one another (directly opposite) – can interfere, and must therefore be on different channels. Houses that are sufficiently far away may use the same wi-fi channel. Your goal is to find the minimum number of different channels the neighbourhood requires. (a) Model this as a graph problem. Remember to: (i) Clearly define the vertices and edges of your graph. 4 marks (ii) State the associated graph problem that you need to solve. 2 marks (b) Give the solution to the graph problem corresponding to this scenario; and determine the minimum number of wi-fi channels required for the neighbourhood? 2 marks (c) How do your answers to (a) and (b) change if a house’s wireless network can also interfere with those of the houses to the left and right of the house over the road? 4 marks Problem 4 (12 marks) This is the Petersen graph: 0 1 2 3 4 5 6 7 8 9 (a) Give an argument to show that the Petersen graph does not contain a subdivision of K5. 6 marks (b) Show that the Petersen graph contains a subdivision of K3,3. 6 marks 4 Problem 5 (20 marks) Let R ✓ S⇥ S be any binary relation on a set S. Consider the sequence of relations R0,R1,R2, . . ., defined as follows: R0 := I = {(x, x) : x 2 S}, and Rn+1 := Rn [ (R;Rn) for n 0 (a) Prove that for all i, j 2 N, if i j then Ri ✓ Rj. Hint: Let Pi(j) be the proposition that Ri ✓ Rj and prove that Pi(j) holds for all j i. 4 marks (b) Let P(n) be the proposition that for all m 2 N: Rn;Rm = Rn+m. Prove that P(n) holds for all n 2 N. Hint: Use results from Assignment 1 4 marks (c) Prove that if there exists i 2 N such that Ri = Ri+1, then Rj = Ri for all j i. 4 marks (d) If |S| = k, explain why Rk2 = Rk2+1. 2 marks (e) If |S| = k, show that Rk2 is transitive. 2 marks (f) If |S| = k show that Rk2 is the minimum (with respect to ✓) of all reflexive and transitive relations that contain R. 4 marks Remark The relation at the limita as n tends to infinity, R⇤ = limn!• Ri, is known as the reflexive, transitive closure of R, and is closely connected to the Kleene star operator. aBecause Rj ✓ Ri ✓ S⇥ S for all j i, the Knaster-Tarski theorem ensures this limit always exists, even for infinite S. Problem 6 (20 marks) A binary tree is a data structure where each node is linked to at most two successor nodes: If we include empty binary trees (trees with no nodes) as part of the definition, then we can simplify the description of the data structure. Rather than saying a node has 0, 1, or 2 successor nodes, we can instead say that a node has exactly two children, where a child is a binary tree. That is, we can abstractly define the structure of a binary tree as follows: • (B): An empty tree, t • (R): An ordered pair (Tleft, Tright) where Tleft and Tright are trees. 5 So, for example, the above tree would be defined as the tree T where: T = (T1, T2), where T1 = (T3, T4) and T2 = (T5, t), where T3 = T4 = T5 = (t, t) That is, T = ⇣ (t, t), (t, t)
,
(t, t), t ⌘ A leaf in a binary tree is a node that has no successors (i.e. it is of the form (t, t)). A fully-internal node in a binary tree is a node that has exactly two successors (i.e. it is of the form (T1, T2) where T1, T2 6= t). The example above has 3 leaves (T3, T4, and T5) and 2 fully-internal nodes (T and T1). For technical reasons (that will become apparent) we assume that an empty tree has 0 leaves and 1 fully-internal nodes. (a) Based on the recursive definition above, recursively define a function count(T) that counts the number of nodes in a binary tree T. 4 marks (b) Based on the recursive definition above, recursively define a function leaves(T) that counts the number of leaves in a binary tree T 4 marks (c) Based on the recursive definition above, recursively define a function internal(T) that counts the num- ber of fully-internal nodes in a binary tree T. 4 marks (d) If T is a binary tree, let P(T) be the proposition that leaves(T) = internal(T)+ 1. Prove that P(T) holds for all binary trees T. Your proof should be based on your answers given in (b) and (c). 8 marks Problem 7 (4 marks) Let S be a finite set, totally ordered by <. Give a formal, recursive definition of the lexicographic ordering lex✓ S⇤ ⇥ S⇤. 4 marks