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

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 C 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:

ak e N  Vn e N  ╱(2n - 1 e P) → (n < k)、

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.

(d) Let B = {0, 1}8 ; for convenience we shall write b1 b2 . . . b8  as shorthand for (b1 , b2 , . . . , b8 ).  Let η : B → Z be defined by the following rule

Vb1 b2 . . . bn  e B  η(b1 b2 . . . 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 “two’s 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.

Problem 2 (10 marks)  (a) We define a sequence (an )neN  by

, a1  = 1

．．  Vn e N an+1  = an  ╱ 1 - 、 .

Use mathematical induction to prove that

n + 1

(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 e p(U), we have    A n (B u Cc ) = (A n B) u (A \ C).

(ii) For any universal set U and for any A, B, C, D e p(U), we have:

If C C A and D C B, then (A × B) \ (C × D) = (A \ C) × (B \ D).

Given any statement variables p, q, and r, a tautology t logical equivalences hold.

and a contradiction c, the following

p v q = q v p

(p v q) v r = p v (q v r)

p v (q A r) = (p v q) A (p v r) p v c = p

p A -p = c

p v p = p

p A c = c

-(p v q) = -p A -q

p A (p v q) = p

-c = t

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 friend’s 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?

(c) For any k e N, an XY-path of length k in the Euclidean plane is a sequence of points ╱(xn , yn )、ne{0,1,2,...,k4  C Z × Z

such that

Vn e {0, 1, 2, . . . , k - 1}  ╱ (xn+1, yn+1) = (1 + xn , yn )、v ╱ (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.

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.

A

B 

E

D

C

(b) Let M be the graph shown below. Prove that M does not have a subgraph isomorphic to K3,4 .

A

C

G  

E

(c) Let n e 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.

Problem 5 (10 marks)  (a) Describe the input and output of Dijkstra’s algorithm.

(b) Let S be the set of connected weighted simple graphs with 4 vertices.  Prove or disprove the following statement:

VG e S  a! T e S  (T is a minimal spanning tree of G).

(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 colleague’s 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.

(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).

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.

(c) Let n e 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 n×1 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.