MAT1830 - Discrete Mathematics for Computer Science Assignment #10 To be handed in at the beginning of your support class in week 12 (21 -25 May) I. Rewrite the following expressions without using ? or ? (a) L (b) II( 2i)'-i-1) [Answer only required.] [2 2. Rewrite the following expressions using ? or ? notation (a) x(x +1(4)( 9) (x 16)(x+400) [Answer only required.] [4] 3. Call a string of letters "legal" if it can be produced by concatenating (running together) copies of the strings 'a', 'bb' and 'cc'. For example, 'abba' is legal because it can be produced by concatenating 'a', 'bb' and 'a', but 'ccca' is not legal. For each integer n let tn be the number of legal strings with n letters. For example, t,-1 ('a' is the only legal string) and t2 = 3 ('aa'W and ce' are the legal strings) (a) Write down tg and a list of all the legal strings of length 3 (b) Write down t4 and a list of all the legal strings of length 4 (c) Find a recurrence for tn that holds for all n2 3. Explain why your recurrence gives t [Answer only required for (a) and (b). Full justification required for (c).] [8 4. Draw simple graphs with the following properties or explain why they do not exist (a) The list of vertices is: P, Q, R, S, T and the list of edges is PQ, PS, QR, RS, RT (b) The graph has 10 vertices and 47 edges (c) The graph has 7 vertices and 6 edges and is connected (d) The graph has 7 vertices and 11 edges and its vertices can be divided into two sets iin such a way that no edge joins two vertices in the same set Picture or explanation required for each part.] 6] 1Connected means that you can "walk from any vertex to any other vertex along the edges. It is defined formally in lecture 30