MATH1005/MATH6005 Discrete Mathematical Models Final Exam, Semester 1, 2021 

 Photo Credit: Amithi Aparekka Liyanagamage. 1 Throughout this exam, we write N for the set of positive integers and N for the set of non-negative integers; that is, N = {1,2,3,...} and N = {0,1,2,...}. Problem 1 (10 marks) (a) Give an example of a statement that has the logical structure of an implica- tion. Then write down the contrapositive, the converse and the inverse of your statement. Clearly label which statement is which (original, contrapositive, converse, inverse). (b) Suppose that A and B are non-empty sets and that R A B. What else must be true about R before we can say that R is an injective function? (c) Let P denote the set of prime numbers. Let s denote the following statement: kN nN (2n 1P)(nk) The statement s is a famous conjecture in Number Theory. Write down a statement that is logically equivalent to s and in which the symbol does not appear. 2 (d) Let B = {0, 1}8; for convenience we shall write b1b2 . . . b8 as shorthand for (b1, b2, . . . , b8). Let : B Z be defined by the following rule b1b2 ...bn B (b1b2 ...bn) = (1)b1 b2 26 +b3 25 +b4 24 +b5 23 +b6 22 +b7 21 +b8 20. Let : B Z be the function that maps each element of B to the integer that it represents using the 8-bit signed integer method (also known as the twos complement method, and the toggle-plus-one method). (i) Evaluate (10100011). (ii) Use set-roster notation to describe the range of and the range of . (iii) Give two reasons why may be preferred to as a method for representing integers in a computer. 3 Problem 2 (10 marks) (a) We define a sequence (an)nN by a 1 = 1 nNan+1 =an 1(n+1)2 . Use mathematical induction to prove that n N an = n + 1. 2n 1 4 (b) Use the logical equivalences below and the definitions of set operations to prove, or provide a counterexample to disprove, each of the following statements. (i) For any universal set U and for any A,B,C P(U), we have A (B Cc) = (A B) (A \ C). (ii) For any universal set U and for any A,B,C,D P(U), we have: IfCAandDB, then(AB)\(CD)=(A\C)(B\D). Given any statement variables p, q, and r, a tautology t and a contradiction c, the following logical equivalences hold. 1. Commutativelaws: pqqp 2. Associativelaws: (pq)rp(qr) 3. Distributivelaws: p(qr)(pq)(pr) 4. Identitylaws: ptp 5. Negationlaws: ppt 6. Double negative law: (p) p 7. Idempotentlaws: ppp 8. Universalboundlaws: ptt 9. DeMorganslaws: (pq)pq 10. Absorptionlaws: p(pq)p 11. Negationsoftandc: tc pqqp (pq)rp(qr) p(qr)(pq)(pr) pcp ppc ppp pcc (pq)pq p(pq)p ct 5 Problem 3 (10 marks) (a) You and your friend are playing a board game. Each turn involves rolling three six-sided dice. The faces of each die are numbered 1, 2, 3, 4, 5, 6. Your friend, who is very reasonable but has not taken MATH1005/MATH6005, makes the following remark These dice may be unfair. With three dice we can roll 16 different totals, so each total should appear every 16-th turn or so. However, we have been playing for hours and the total 18 has hardly ever come up. In no more than five sentences, respond to your friends statement. An excellent response will either agree or disagree with the reasoning in the statement, and will justify the position taken so clearly that your friend is likely to agree with you. (b) A PIN is a string of 4 digits. A PIN is said to be non-repeating if no digit appears twice. For example, 3137 is a PIN, while 0216 and 7935 are non-repeating PINs. What is the probability that, when a PIN is selected at random, it is a non-repeating PIN in which the digits appear in strictly increasing order? 6 (c) For any k N, an XY-path of length k in the Euclidean plane is a sequence of points (xn, yn) n{0,1,2,...,k1} (xn+1,yn+1)=(1+xn,yn)(xn+1,yn+1)=(xn,1+yn); we say that such a path starts at (x0, y0) and ends at (xk, yk). From all of the XY-paths that start at (0, 0) and end at (4, 6), one is chosen at random. What is the probability that the chosen XY -path visits the point (2, 0)? Give your answer as a decimal, correct to two decimal places. such that n{0,1,2,...,k} Z Z 7 Problem 4 (10 marks) Graph Theory (a) Let G be the graph shown below. Use set-roster notation to write down a set V (G) and a multiset of size-2 multisets E(G) that together describe G, and also write down an adjacency matrix that describes G. AB E DC (b) Let M be the graph shown below. Prove that M does not have a subgraph isomorphic to K3,4. AB HC GD FE 8 (c) Let n N. The hypercube of dimension n, denoted Hn, is the simple graph such that: V (Hn) is the set of length-n bit strings; two length-n bit strings are adjacent if and only if the bit-strings differ in exactly one position. (i) How many vertices does Hn have? (ii) What is the degree of each vertex in Hn? (iii) How many edges does Hn have? (iv) If there exists a Hamilton circuit in H4, write one down; if no Hamilton circuit exists in H4, explain how you know. 9 Problem 5 (10 marks) (a) Describe the input and output of Dijkstras algorithm. (b) Let S be the set of connected weighted simple graphs with 4 vertices. Prove or disprove the following statement: GS !T S (T isaminimalspanningtreeofG). (c) Suppose that you are given a weighted digraph G that represents a transport network, and your colleague says At any time, we can make at most 20 units flow through this network. Your friend then shows you an example of a flow of volume 20 across the network. One way to check your colleagues statement is to apply one of the algorithms we learned in the course. Describe another method by which you may determine whether your colleagues statement is true or false, and justify why your method will allow you to be confident in your answer. 10 (d) Use the vertex labelling algorithm described in the course to find a maximum flow function for the transport network shown below (pseudocode for this algorithm is given at the end of the exam paper). The first incremental flow f1 is shown in the first row of the table at the bottom of the page, and the cumulative flow F1 is shown in the graph. Write down the subsequent incremental flows in the table (use only as many rows as you need). b 4, 0 c 4, 0 4, 2 s 2,2 t 6, 2 a 6, 0 f1 sact 2 6, 0 d incremental flow label path of incremental flow volume of incremental flow 11 Problem 6 (10 marks) (a) In no more than three sentences, explain how an internet is modelled by some type of graph (called a webgraph) for the purposes of the PageRank algorithm. An excellent answer will detail what type of graph is used, what the vertices represent, and what the edges represent? (b) The PageRank algorithm may be understood to be following the movement of The Random Surfer. In no more than five sentences, explain how The Random Surfer moves around the internet. 12 (c) Let n N, let G be a webgraph with n vertices, let = 0.15 and let M denote the modified transition matrix (in the PageRank algorithm) determined by G and . In the box below, write down an equation that completes the definition of the PageRank vector PR for G and . The PageRank vector PR is the unique n1 matrix such that its entries sum to 1 and the following equation is satisfied (d) Let G be the webgraph with the adjacency matrix A shown below. Draw a picture of the graph G represented by A, and then write down the basic transition matrix T associated to A as part of the PageRank algorithm. 011010 101000 0 1 0 1 1 1 A=0 0 1 0 0 0 000000 010010 THIS IS THE END OF THE EXAM. PSEUDOCODE FOR THE VERTEX LABELLING ALGORITHM IS OVER THE PAGE. 13 Vertex labelling algorithm for finding a maximum flow function for a transport network Input: Transport network D with capacity function C. Output: A maximum flow function Fmax for the network. Method: Initialise F to the zero flow F0. Initialize i to 1. For i = 1, 2, . . . carry out stage i below to attempt to build an incremental flow fi. If stage i succeeds, define Fi = Fi1 + fi and proceed to stage i+1. If stage i fails, define Fmax = Fi1 and stop. Stage i: 1. If i > 1, mark up the amended edge flows for Fi1. 2. Mark up the levels for Fi1, as explained below. 3. If t is assigned a level, stage i will succeed, so continue. If not, then stage i fails, so return above to define Fmax and terminate. 4. Mark up labels for Fi1 as follows until t is labelled: (a) Label each level 1 vertex v with skv, where kv = S((s,v)). (see below for definition of S) (b) If t has level 2 or more now work through the level 2 vertices in alphabetical order, labelling each vertex v with uku, where u is the alphabetically earliest level 1 vertex with (u,v) E(D) and S((u,v)) > 0, kv is the minimum of S((u,v)) and the value part of us label. (c) If t has level 3 or more now work through the level 3 vertices in a similar manner and so on. 5. Letpi bethepathu0u1...un whereun =tandfor0<jn uj haslabeluj1kj. Define fi to be the incremental flow on pi with flow value kn. End of Method Levels and labels: At each stage of the vertex labelling algorithm levels and labels are associated afresh with the vertices of the network. The level of a vertex is determined iteratively as follows: The source vertex s always has level 0. Ife=(s,x)andS(e)>0thenxhaslevel1. If x has level n and S((x, y)) > 0 then y has level n + 1 provided it has not already been assigned a lower level. The label on a vertex v of level n 1 has the form uk, where u is a vertex of level n 1 and (u, v) E(D) is an edge on the path for a potential incremental flow through v with flow value k. The algorithm assigns labels in ascending order of levels, and in alphabetical order within levels. The spare capacity function S For vertices u,v of D, where D has capacity and flow functions C,F: C((u,v))F ((u,v)) S((u,v)) = F ((v,u)) 0 When (v,u) E(D), S((u, v)) is called a virtual capacity. if (u,v) E(D) if (v,u) E(D) otherwise. 14