MATH6005 Graduate Assignment B, 2020 ANU Total Marks: 30 Value: 5% of final grade Due: 11pm Sunday 17 May 2020 This assignment is based on Part B (Digital Information). Please upload your solutions in PDF format, using the link provided. If you write the solutions by hand, you will need to scan your work and save it as a pdf file. Page 1 of your solutions document should be a ‘cover page’ containing only: 1. Title: “Graduate Assignment B” 2. Your full name, with surname in upper case. 3. Your ANU ID 4. The declaration: “I have read the ANU Academic Skills statement regarding collusion.” (https://www.anu.edu.au/students/academic-skills/academic-integrity/plagiarism/collusion) “I have not engaged in collusion in relation to this assignment”. 5. Your signature. (If you are typesetting rather than scanning a hand-written document, you can type your name and it will be deemed a signature.) 6. The date and approximate time of your submission. Regarding item 4, I emphasise the last paragraph of the Academic Skills statement: The best way people can help each other to understand the material is to discuss the ideas, questions, and potential solutions in general terms. However, students should not draw up a detailed plan of their answers together. When it comes to writing up the assignment, it should be done separately. If collusion is detected, all students involved will receive no marks. You may find some questions more difficult/time-consuming than others. Marks per question are indicated but are not necessarily an indication of difficulty or length. Question 1 [6 marks] A new 16-bit standard for storing floating point numbers, called bfloat16, has become popular in the last couple of years for use in machine learning programs. It is a trun- cated form of single precision floating point (which uses 32 bits) but is different to half precision floating point (which also uses 16 bits). Please read the Wikipedia article https://en.wikipedia.org/wiki/Bfloat16_floating-point_format before attempt- ing the questions below. The article is self contained, so it is not necessary to first know the details of single precision floating point. For the questions below, show how you obtain your answer – do not use an on-line converter! (a) What is the value (expressed in decimal notation) of the number stored in bfloat16 format as FADE16? (b) What is the (very small) value of the number stored in bfloat16 format as 800816? Express your answer in decimal scientific form with two decimal places. Careful! (c) In bfloat16 format, the word 7FC016 does not store a number. Why not? (d) and (e) on next page Page 1 of 5. MATH6005 Graduate Assignment B, 2020 ANU (d) When one million is stored (approximately) in bfloat16 format, what is the exact (decimal) value of the number stored? (e) The bfloat16 format is not recommended for storing integer values. What is the least n ∈ N which cannot be stored exactly in bfloat16 format? Question 2 [6 marks] Charlie wants you to guess his mobile ’phone number. Like all such Australian numbers, it is ten digits long, starting with 0. He keeps giving you clues about the remaining nine digits, but you respond by telling him how many numbers satisfy the clue, so it’s still too hard to guess. Calculate how many mobile ’phone numbers satisfy each of the conditions. The clues are increasingly more specific, so the numbers should steadily reduce from many millions down to less than a hundred. Here are the clues: (a) There are an odd number of odd digits and an even number of even digits. (b) Three of the digits are odd and six are even. (c) There are two 2’s, three 3’s and four 4’s. (d) The two 2’s are not adjacent to each other. (e) Neither are any of the three 3’s adjacent to each other. (f) In fact, no two adjacent digits are the same. Slightly cryptic hints: (a) Think twice before considering lots of different cases; there is no need. Should the last digit be odd, or should it be even? It depends, doesn’t it? (b) Where do the odd digits go? (c) Remember MILLIMICRON? (d) Compl(i)(e)mentary advice: double2 could be a new digit! (e) Triple3 is troublesome. (f) Probably best to invent your own counting method here. Page 2 of 5. MATH6005 Graduate Assignment B, 2020 ANU Question 3 [6 marks] A popular method of sorting a sequence is called Insertion Sort (or InsertionSort). You can read about it in our recommended textbook1 by Epp in §11.3 (4&5ed), §9.3 (3ed) and on many websites including Wikipedia https://en.wikipedia.org/wiki/Insertion_sort and Khan Academy https://www.khanacademy.org/computing/computer-science/ algorithms/insertion-sort/a/insertion-sort. (That one has a nice slow animation.) Here is a slightly modified version of an algorithm for Insertion Sort given in Epp: INPUT: Natural number n, a sequence (ai)1..n ⊆ S and an ordering rule ≺ for S. OUTPUT: The members of the sequence (ai)1..n reordered into a new sequence in non-decreasing order with respect to ≺. METHOD: i← 2 (i is the item counter) while i ≤ n x← ai (x holds the next item to be inserted) j ← i − 1 (j marks the position of the item to which x is to be compared) while j ≠ 0 if x ≺ aj (should x be moved left (again) ? ) then aj+1 ← aj (yes, so slide aj right) j ← j − 1 else aj+1 ← x (no, insert x here) j ← 0 end if end while i← i + 1 end while END METHOD (a) Apply the algorithm to sort the sequence F,D,C,E,B,C into alphabetical order. Show the state of the sequence each time the ‘i ≤ n’ test in line 2 of the method is performed. (b) How many item comparisons ‘x ≺ aj’ are performed for the application (a)? (c) In no more that 50 words compare the efficiencies of Selection Sort and Insertion Sort, mentioning any situations where one is superior to the other. Be sure to reference any sources you use for your answer. (References are not included in the word count.) (d) Rewrite the algorithm using indirect addressing, so that no sequence items are actually moved. The INPUT should be unchanged, but the OUTPUT should now read: OUTPUT: A permutation pi ∶ {1, .., n}→ {1, .., n} for which the sequence (api(i))1..n is in non-decreasing order with respect to ≺. 1Susanna Epp: Discrete Mathematices with Applications. Cengage 1990-2020 Page 3 of 5. MATH6005 Graduate Assignment B, 2020 ANU Question 4 [12 marks] Some applications of mathematics require the use of very large matrices (several thousand rows for example) and this in turn directs attention to efficient ways to manipulate them. This question focuses on the efficiency of matrix multiplication, counting the number of numerical arithmetic operations (addition, subtraction and multiplication) involved. We start with very simplest case of 2×2 matrices. (a) The standard way of multiplying 2×2 matrices uses 8 multiplications and 4 additions. List the 8 products for [a b c d ] [s t u v ] . (b) In a landmark paper of 19692, Volker Strassen surprised the mathematical community by showing how to multiply 2×2 matrices using only 7 multiplications. For the matrix product in (a) the seven products are: p1 = (a + d)(s + v) p2 = (c + d)s p3 = a(t − v)p4 = d(u − s) p5 = (a + b)vp6 = (c − a)(s + t) p7 = (b − d)(u + v) and then [a b c d ] [s t u v ] = [w x y z ], where w,x, y, z are given by: w = p1 + p4 − p5 + p7 x = p3 + p5 y = p2 + p4 z = p1 − p2 + p3 + p6. Illustrate the use of this method replacing a, b, c, d with 2,3,5,7, and s, t, u, v with−7,3,5,−2. Show the values of p1, . . . , p7 and w,x, y, z. Check the result using standard matrix multiplication. (c) Strassen’s method saves one multiplication at the cost of adding a lot more addi- tions/subtractions. So at first sight it does not appear to be at all efficient. However, the efficiency improves for larger matrices when the method is combined with a ‘divide-and-conquer’ strategy. This strategy partitions 2n×2n matrices into n×n quarters so that the multiplcation of a pair of 2n×2n matrices can be replaced by a series of multiplications and additions of n×n matrices. Consider this 4×4 example: M = ⎡⎢⎢⎢⎢⎢⎢⎢⎣ 1 0 2 −3 3
−1 0 −2 1 −3 2 0−3 2 0 1 ⎤⎥⎥⎥⎥⎥⎥⎥⎦ = ⎡⎢⎢⎢⎢⎢⎢⎢⎣ 1 0 2 −3 3 −1 0 −2 1 −3 2 0−3 2 0 1 ⎤⎥⎥⎥⎥⎥⎥⎥⎦ = [A B C D ] N = ⎡⎢⎢⎢⎢⎢⎢⎢⎣ 2 3 −2 3 3 −1 0 2−1 0 1 0 0 2 −3 −1 ⎤⎥⎥⎥⎥⎥⎥⎥⎦ = ⎡⎢⎢⎢⎢⎢⎢⎢⎣ 2 3 −2 3 3 −1 0 2− 1 0 1 0 0 2 −3 −1 ⎤⎥⎥⎥⎥⎥⎥⎥⎦ = [S T U V ] MN = ⎡⎢⎢⎢⎢⎢⎢⎢⎣ 1 0 2 −3 3 −1 0 −2 1 −3 2 0−3 2 0 1 ⎤⎥⎥⎥⎥⎥⎥⎥⎦ ⎡⎢⎢⎢⎢⎢⎢⎢⎣ 2 3 −2 3 3 −1 0 2−1 0 1 0 0 2 −3 −1 ⎤⎥⎥⎥⎥⎥⎥⎥⎦ = ⎡⎢⎢⎢⎢⎢⎢⎢⎣ 0 −3 9 6 3 6 0 9−9 6 0 −3 0 −9 3 −6 ⎤⎥⎥⎥⎥⎥⎥⎥⎦ = ⎡⎢⎢⎢⎢⎢⎢⎢⎣ 0 −3 9 6 3 6 0 9− 9 6 0 −3 0 −9 3 −6 ⎤⎥⎥⎥⎥⎥⎥⎥⎦ = [W X Y Z ] Using only 2×2 matrices and the standard method (not Strassen) of matrix multiplication, verify that: [A B C D ] [S T U V ] = [W X Y Z ] . (i.e. verify that AS +BU = W etc.) (d) What is the total number of arithmetic operations (multiplications and additions of numbers) used to calculate the product MN in (c)? Is there any saving in using partitioning over direct 4×4 multiplication? Show how you arrive at your answer. (e) Generalise your answer to (d) to give a formula for the number of arithmetic operations used to calculate the product of a pair of n×n matrices using the standard method. 2Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969 Page 4 of 5. MATH6005 Graduate Assignment B, 2020 ANU (f) It is time to look at what happens when, as foreshadowed in (c), Strassen’s 2×2 method is combined with partitioning, to deal with larger matrices. (Matrix multiplication using partitioning works for any size matrices.) For convenience, we consider only n×n matrices for n a power of 2, say n = 2r, r ≥ 0. (As in the analysis of MergeSort, this requirement and can easily be avoided in practice.) To multiply a pair of these matrices (with r ≥ 1) we first partition them into quarters A, . . . ,D, S, . . . ,V and then apply Strassen’s formulae using these quarters, starting by calculating the product P1 = (A +D)(S +V). But this (matrix) product, and the other six, are, recursively, calculated by the same process. By continually halving the dimensions of the matrices in this way we eventually arrive at 1×1 matrices, that is, we just multiply numbers. Now let F (n) denote the number of arithmetic operations (multiplications, additions and subtractions of numbers) used during this process to compute the product of a pair of n×n matrices. An implicit formula for F (n) is: F (1) = 1; F (2n) = 7F (n) + 18n2. Give a justification/derivation of this implicit formula. (g) Use mathematical induction on r to prove that ∀n ∈ N⋆ F (2r) = 7r+1 − 6(4r). (h) For 4×4 matrix multiplication the Strassen-partitioning process uses more then twice as many arithmetic operations than the standard method. But the ratio starts reducing for larger matrices. (i) What is the least value of n = 2r for which the Strassen-partitioning process uses less arithmetic operations to multiply a pair of n×n matrices than does the standard method? (ii) What is the least value of n = 2r for which the Strassen-partitioning process uses less than half the number of arithmetic operations to multiply a pair of n×n matrices than does the standard method? (iii) Approximately how many operations does the Strassen-partitioning actually use for the cases you found for (i) and (ii)? Answer to the nearest million, billion, trillion, quadrillion etc as appropriate. Justify your answers. Use of a spreadsheet or on-line calculator is recommended. End of Questions for Assignment B Page 5 of 5.
