首页 >
> 详细

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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Csse1001 Assignment 3 2021-01-10
- Comp3506/7505 Homework 4 – Graph Algo 2021-01-10
- Unix & C Programming (Comp1000) Assign... 2021-01-10
- Ece 209 Program 3: Market 2021-01-10
- Informatics 1 — Functional Programming 2021-01-10
- Cisc/Cmpe 452/Cogs400 Assignment 2 2021-01-10
- Fit2100 Operating Systems Assignment #... 2021-01-10
- Csci 1100 — Homework 5 2021-01-10
- Comp9444 Neural Networks And Deep Lea... 2021-01-10
- Assignment Case: German Credit 2021-01-10
- 48024 Applications Programming Assign... 2021-01-10
- Cs 405/805-001: Computer Graphics Ass... 2021-01-10
- Cse 434, Sln 70608 — Computer Networks 2021-01-10
- Corpfin 2503 - Business Data Analytics 2021-01-10
- Cis 455 / 555: Internet And Web System... 2021-01-10
- Cs110留学生编程代写、代做c++程序实验、Program程序语言调试帮做 2021-01-10
- Csc8021程序代做、代写networks编程语言、代做c/C++，Jav 2021-01-10
- 代写program编程语言、代做python，C++，Java程序设计帮做j 2021-01-10
- R编程课程代写、代做program程序语言、R程序实验代做代写databas 2021-01-09
- Data编程设计代做、代写java程序语言、Java程序实验调试代写r语言程 2021-01-09