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 (45ed), §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.