MATH6005 Graduate Assignment B, 2021 ANU
Question 1 (You may wish to write code to answer these questions)
If p is a prime, and g is an integer from the set {1,2, . . . , p − 1}, we say that g is a
companion of p when
{ga mod p a ∈ Z and 1 ≤ a < p} = {1,2, . . . , p − 1}.
(A) Find all of the companions of 11. Justify your answer.
(B) Describe how you would go about proving or disproving the following statement:
104651 is prime and 24578 is a companion of 104651.
(C) Here is a four-step method to quickly compute gs modulo p without ever computing
or storing a number that exceeds p2:
Step (1) Complete a table of values like the one below, where m is the largest
power of 2 that does not exceed p:
t gt mod p
1
2
4
8
16⋮
m
Step (2) Write s as a sum of powers of 2 (this is like finding a representation of s
in binary).
Step (3) Use the result of Step (2) to find integers x1, x2, . . . , xc such that
gs mod p = x1x2 . . . xc mod p
and each each xi is in the right-hand column of the table you made in part
Step (1).
Step (4) Evaluate gs mod p by completing a table like the one below:
x1x2 mod p =(x1x2)x3 mod p =(x1x2x3)x4 mod p =⋮ ⋮(x1x2x3 . . . xc−1)xc mod p =
Let p = 104651, g = 24578 and s = 100418. Compute gs mod p, showing all your
working. In your working you should never compute or write down a number that
exceeds p2.
(D) Let s be an integer such that 1 ≤ s < 104651 and
24578s mod 104651 = 3190
Find s and explain how you found it.
Page 3 of 5.
MATH6005 Graduate Assignment B, 2021 ANU
Question 2 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 truncated form of single precision floating point (which uses 32 bits) but is di↵erent
to half precision floating point (which also uses 16 bits). Please read the Wikipedia ar-
ticle https://en.wikipedia.org/wiki/Bfloat16_floating-point_format before at-
tempting 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 con-
verter!
(A) What is the value (expressed in decimal notation) of the number stored in bfloat16
format as BADE16?
(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) 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?
Page 4 of 5.
MATH6005 Graduate Assignment B, 2021 ANU
Question 3 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 ← −1
end if
end while
if j = 0 then a1 ← x (if x has not yet been inserted, insert it now)
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 eciencies 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 actu-
ally moved. The INPUT should be unchanged, but the OUTPUT should now read:
OUTPUT: A permutation ⇡ ∶ {1, .., n} → {1, .., n} for which the sequence (a⇡(i))1..n
is
in non-decreasing order with respect to .
End of Questions for Assignment B
1Susanna Epp: Discrete Mathematices with Applications. Cengage 1990-2020
Page 5 of 5.

欢迎咨询51作业君