MATHEMATICS _ w & STATISTICS MAS225 OPTIMISATION AND GRAPH THEORY Assignment 2 Due by 5:00pm (AWST), Friday October 4, 2024 Total Marks: 36 1. 4. [3 marks] Write out the multiplication table for Zg. It is a field? Explain your answer. . [8 marks| Consider the code C = {001110, 110001, 001001, 110110}. (a) Find an error pattern with weight 3 that C cannot detect. (b) Does C correct the error pattern 0011007 () Find an error pattern with weight 2 that C cannot correct. (d) Find the minimum distance of C, and hence determine for which value of k the code is k-error-correcting. . [10 marks] Consider S = {110001,001110,001001, 110110} C Z3. (a) What is the dimension of the span of 57 (b) Is B = {110001,001110,001001} a basis for the linear code spanned by S? () Form a matrix G which has the vectors from B as its rows. Assign characters to each of the words in Z3 as follows: + A K N O T Y 000 001 010 011 100 101 110 111 and use G to encode the message: STONKST. (d) What is the minimum distance of the the linear code spanned by S7 (e) Decode the following message which was encoded using S, with characters as- signed to codewords as in part (c), and then received with some errors (within the correcting capacity of the code): 111001 111111 001001 100111 001110 110110 Consider the following LP problem: Minimise z = 5x1 + 6x2 Subject to: 2x1 + x2 -10 vV IV 1 + 2:)3'2 IA =) 571 T2 2 IA and xy, T2 > 0. (a) [10 marks] Solve the LP model graphically to find optimal x;, x5, and z. (b) [5 marks] Rewrite the LP model in Standard form. No further questions