Calculate the transition matrix of graph and give the graph

Question

1. (a) Consider the following algorithm for calculating a check digit. Given the number a₁, a₂, a₃, . . . , a₈, calculate the check digit a₉ so that

9a₁ + 3a₂ + 7a₃ + 3a₄ + 7a₅ + 9a₆ + 7a₇ + 9a₈ + 3a₉ ≡ 0 mod 10.

i. Given b₁, b₂, . . . , b₈, find b₉ using this algorithm.

ii. Is the identification number 5,1,2,9,7,8,2,6,4 valid? Prove your assertion.

iii. Is the identification number 1,2,5,9,7,8,2,6,3 valid? Prove your assertion.

iv. Suppose that

a₁, a₂, a₃, a₄, a₅, a₆, a₇, a₈, a₉

and

a₂, a₃, a₁, a₄, a₅, a₆, a₇, a₈, a₉

are both correctly recorded.

What is the congruence equation satisfied by a₁, a₂ and a₃?

Give a value of a₁ that satisfies this congruence equation if a₂ = 1 and a₃ = 3.

Is your value of a₁ unique? Prove your assertion.

(b) Suppose that a group of people want to be able to communicate securely amongst themselves using a public channel.

i. For the RSA cryptosystem suppose that Bob's public key is given by e = 7 and n = 341. If Alice wants to send the message m = 39 to Bob, what is the corresponding value of c?

ii. Determine d in this case.

iii. Given another valid pair for d and e when n = 341.

iv. Use your d and e to encode b1, b2, b3, b4.

2. (a) Consider the generator matrix

G = 1 0 1 0 1

      0 1 0 1 1

for a binary code.

i. Give the parity check matrix that corresponds to this generator matrix.

ii. Give the 4 messages possible, and the corresponding codewords.

iii. Give the coset corresponding to the sequence (0, 0, 0, 0, 1). Is this coset leader unique? Give the syndrome corresponding to each valid coset leader of this coset.

iv. Give the coset corresponding to the sequence (1, 1, 0, 0, 0). Is the coset leader unique? Give the syndrome corresponding to each valid coset leader of this coset.

v. What are the consequences for decoding if there is more than one possible coset leader?

(b) If the binary code C has d(C) = 4, how many errors can it detect?

(c) If the binary code C has d(C) = 4, how many errors can it correct?

(d) If the binary code C has d(C) = 5, how many errors can it detect?

(e) If the binary code C has d(C) = 5, how many errors can it correct?

(f) Consider the two codewords cbaaa and cbbab from a ternary code based on the alphabet a, b and c.

i. What is the Hamming distance between these two codewords?

ii. Give a sequence of length 5 which is distance 1 from each of these codewords.

iii. Give a sequence of length 5 which is distance 1 from the first codeword and at least distance 3 from the second.

(g) Suppose that m = 2 and that we transmit two binary digits with no check symbols. Suppose that the probability that a digit is correctly transmitted is p, and let q = 1 - p.

i. Show that the proportion of received messages containing errors is 1 - p².

ii. Will any of these be detected? Explain your answer in a sentence.

iii. Suppose that we transmit two binary digits together with a parity check digit. What is transmitted for the message 01?

iv. Show that the proportion of received messages containing errors is 1 - p³.

v. What is the proportion of errors passing undetected through the system?

vi. Given that an error has been made, what is the probability of an undetected error?

3. (a) Give the equations satisfied by the intersection numbers x₀, x₁, x₂, x₃ and x₄ for a (9, 18, 8, 4, 3) BIBD.

(b) Assume that x₄=0. Give all possible solutions for these equations.

(c) For each of your solutions assume that the given block is 0 1 2 3. For the remaining 17 blocks, indicate where the 0s, 1s, 2s and 3s appear in the BIBD (recall that the order of the blocks is immaterial). Do NOT try to complete these partial designs.

(d) Complete the following array so that it is a self-orthogonal Latin square.

(e) Hence give a spouse-avoiding mixed doubles tournament for 4 couples.

(f) Using the SOLS you have constructed above give an OA[16, 4, 4, 4, 4, 2].

(g) Describe how you can use your OA to define a secret sharing scheme for 3 participants.

4. (a) Give the tree corresponding to the expression

ab + 3/ (f + g)h × (c + d)/gh

(b) Give the post-order traversal of this tree.

(c) Consider a tree with v vertices in which one vertex has degree k. Prove that the longest path in the tree has at most v - k + 1 edges.

(d) Consider the degree sequence

1 1 1 1 1 2 2 5

i. Draw two non-isomorphic 8 vertex trees with this degree sequence.

ii. Why are the trees non-isomorphic?

(e) When considering a directed graph as a representation of a web, we dealt with a vertex with outdegree 0 by assuming that there was a link from such a vertex to every vertex in the graph and hence obtaining the augmented transition matrix S. Another approach is to assume that when a surfer arrives at a web page with no links (edges) out that they will just "hit the back button". To model this bounce back, we added a new vertex for every inlink into each such node. Consider the web graph shown below.

i. Calculate the transition matrix of this graph.

ii. Give the graph that corresponds to "hitting the back button" for this graph.