i had attached the files
MAT1DM/MAT4DM ASSIGNMENT 5, 2020 A 5PM, 21 May Each page of your solutions must carry your name and your student number. Scan your assignment, and submit it as a single pdf file through the LMS. The printers around campus are also scanners. By submitting your work electronically, you are affirming that it is all your own work, and you will be asked to confirm this as you submit it. Assignments are designed to help you master concepts, solve problems and develop your mathematical commu- nication skills. Considerable weight is given to the way you communicate your answers. 1. (a) Apply Kruskal’s algorithm to find a minimal weight spanning tree and its weight for the graph on vertices v1, v2, . . . , v6 with the following edges (and corresponding weights) edge: v1v2 v1v4 v1v5 v2v3 v2v5 v2v6 v3v5 v3v6 weight: 7 8 2 3 4 1 6 5 Set out your answers in a table, as in Practice Class 9A (Questions 4 and 5). (b) Draw your spanning tree on the following set of vertices: v4 v5 v6 v1 v2 v3 2. (a) Draw an expression tree for the following algebraic expression relating to Boolean algebra (use = at the main root): ((y ⇒ x)⇒ (x ∧ y)) = ((x ∨ y) ∧ y). You should not simplify the expression. (b) For the expression tree on the right, give (i) the bracketed infix expression (you may omit brackets at the variables and at the main root), (ii) the bracket-free prefix expression and (iii) the bracket-free postfix expression. = ⇒ ⇒ x y x ∧ x y 3. In each case below, either draw a graph with the required properties, or prove that it doesn’t exist (based on the results of Lecture/Workshop 9 or similar). (a) A tree on 8 vertices with degrees 1,1,1,1,1,2,3,4. (b) A graph on 5 vertices with degrees 1,2,3,4,5. (c) A tree on 7 vertices with degrees 1,1,1,2,4,4,5. (d) A graph on 3 vertices with degrees 1,2,3. (e) A graph without loops or multiple edges on 5 vertices with degrees 1,3,3,3,4. (f) A graph without loops or multiple edges on 5 vertices with degrees 1,2,3,4,4. 4. Give a complete solution, for the second order recurrence relation (no check is required): S(n) = −S(n−1)− 1 4 S(n−2) S(0) = 4, S(1) = −3, (where n ≥ 2) You must include all the relevant words in your solution such as; “Standard Form”, “Homogeneous”, “Characteristic Equation”, “General Solution” and others. You can use abbreviations like . . . Char. eq. . . . Gen. Sol. . . . Hint: you will need to use the“multiply by n-rule” for homogeneous recurrence relations. 5. Consider the first order recurrence relation: Tn = 5Tn−1 + 5 n, T1 = 15, (where n ≥ 2) (a) Calculate T2, T3 and T4 using iteration. Give detailed answers. (b) Give a complete solution, including the check, for the recurrence relation above. You must include all the relevant words in your solution such as; “Standard Form”, “Homoge- neous”, “Characteristic Equation”, “General Solution” and others. You can use abbreviations like . . . Char. eq. . . . Gen. Sol. . . .