MIE335 Winter 2020: Final (Take-home) Exam
April 16, 2pm (EST) to April 17, 2pm (EST)
Last name
First name UTORid Student number
U of T email @mail.utoronto.ca
Question
Points
Score
Inverse
8
Prime
8
Cholesky
14
LU
16
Anagrams Again
17
Hash Hash
17
Not Too Complex
10
Too Complex
10
Total:
100
Instructions:
• During the exam, post your questions only on Piazza.
• Do not ask a question unless you are sure there is a mistake in the problem, or clarifications are absolutely
needed. Before asking for clarifications, make sure that you read the question carefully a few times.
• Written answer instructions:
– Prepare your solutions via whichever method you prefer (such as on paper, tablet, and computer), and upload one .pdf or .jpg for each question as indicated in Crowdmark; note that some parts might have been indicated separately such as Part a and Part b.
– An answer outline/template is provided for each question, you must follow it. We expect your answers in a specific order to ease grading. We are mostly asking you to first summarize the results and then provide explanations.
– You must show all your work; answers without detailed explanations will not receive credit; also insuf- ficient explanations will lead to lost marks.
– Neatness counts. Illegible or unclear answers will not receive credit.
– For any task for which you use coding, you must provide a pseudocode in your written answer, unless
otherwise stated.
• Code instructions:
? Any code you submit should (i) follow the specific instructions provided in the problem description file (e.g., function/script name), (ii) run without any errors “out of the box”, and (iii) run correctly (for the set of instances that we will test). Failure in steps (i) and (ii) will automatically receive 0 points.
– Some files (called “SourceFiles”) are provided for your use in Quercus. If you want to use the source files, it is up to you to figure out what they do and how to use them.
– Submit all your codes (.py) and figures (.pdf or .jpg), if any, ONLY their final versions, via Quercus.
– For any task for which you use coding, unless otherwise stated, you must provide a pseudocode in your
written answer. Any code without a matching pseudocode will be disregarded.
• Violating the instructions will result in an extra 3 point deduction.
Academic Integrity Statement:
“In submitting this assessment, I confirm that my conduct during this exam adheres to the Code of Behaviour on Academic Matters. I confirm that I did NOT act in such a way that would constitute cheating, misrepresentation, or unfairness, including but not limited to, using unauthorized aids and assistance, impersonating another person, and committing plagiarism. I pledge upon my honour that I have not violated the Faculty of Applied Science & Engineering’s Honour Code during this assessment.”
If you have not submitted your answer for the Quercus Quiz on time, to declare that you read all the instructions and approve entirety of its content, and that you will comply with the Academic Integrity Statement, you will not be allowed to take the exam, i.e., your exam will not be graded.
Page 2
Question 1: Inverse ……………………………………………. (8 points)
Compute the results to the following questions by hand. (1) 9 1 mod 70 = ?
(2) 98765 1 mod 125 1 mod 11 = ?
Answer to (1):
Answer to (2):
Detailed Explanation for (1): Detailed Explanation for (2):
Page 3
Question 2: Prime ………………………………………………(8 points) Recall Fermat’s little theorem: If p is prime, then for any integer a not divisible by p, we have ap 1 ⌘ 1 (mod p).
Illustrate the application of the Fermat’s little theorem for a = 5 and a = 7 to check the primality of 6601. (In case needed, modexp2.py is provided. If you use/run it, you don’t need to show its steps; rather mention what output you get and how you use the output.)
(1) Conclusion from the case of a = 5: (2) Conclusion from the case of a = 7:
Detailed Explanation for (1): Detailed Explanation for (2):
Page 4
Question 3: Cholesky ………………………………………….(14 points) For the matrices
29 5 53 29 5 213 29 6 33 A=45 765 B=45 7165 C=4 620 65
5 6 9 23 16 9 3 6 3
find the one that has a Cholesky decomposition and compute its Cholesky decomposition by hand. For the
matrices that do not have a Cholesky decomposition, provide a reason why this is the case.
(1) Matrices without a Cholesky decomposition:
(2) Matrix with a Cholesky decomposition:
(3) The Cholesky decomposition of the suitable matrix:
Detailed Explanation for (1): Detailed Explanation for (2): Detailed Explanation for (3):
Page 5
Question 4: LU ………………………………………………..(16 points) Complete the partially given PLU decomposition of the matrix A below by hand, without any code or
calculator. Clearly explain the steps you have taken.
26 2 1 0 1 37 26 0 0 1 0 37 26 6 1 37 7 26 6 0.5 237 7
A = 64 2 1 2 3 75 = 64 0 1 0 0 75 6 6 0012000164
7 7 6 6 7 7 17564 2 275
4 1 0 2 1 0 0 0
Now, illustrate how to use this decomposition to solve the system of equations Ax = b where b = 64 5 75 .
0 0.5 1 1
8 16
(You can use Python, e.g., numpy.linalg.solve(CoefficientMatrix, RightHandSide), to solve the intermediate systems of equations, no need to solve them manually.)
(Note: If you fail to find the PLU decomposition, clearly explain how you would have solved the given system of equations, for partial credit.)
26 11 37
(1) Matrix L: (2) Matrix U: (3) Solution x:
Detailed Explanation for (1) and (2): Detailed Explanation for (3):
Page 6
Question 5: Anagrams Again …………………………………. (17 points) An anagram is a word or phrase formed by rearranging the letters of a di↵erent word or phrase, using all the
original letters exactly once. Examples include “Arc = Car” and “Python = Typhon”.
54 di↵erent RSA encrypted anagrams are provided in the Anagrams folder in the SourceFiles folder uploaded to Quercus. They are indexed by 0,1,…,53 as the file names suggest; e.g., the file Text0.txt corresponds to the encrypted anagram with index 0. For anagram with index i 2 {0, 1, . . . , 53}, the public key used for its encryption is (N, e) = (Nvalues[i], 17) where the one-dimensional array Nvalues is also provided in the Anagrams folder, and encryption is done character by character using ASCII values.
Pick the anagram with the following index: (Your 10-digit student number) mod 54.
For your selected (anagram) message, find the private key and decrypt it. Provide a detailed explanation on which steps you took to solve the question. If you use any code, in addition to submitting your final code as a single script named anagrams utorid.py, write down a pseudocode for it on paper.
HINT: An example skeleton file decrypt.py is provided. Convert an integer number k to a character with chr(k). Note that modexp2.py function is also provided.
(Note: If you fail to find the private key: Write down/submit your pseudocode/code for decryption, select your own public and private keys, and illustrate encryption and decryption of any anagram you make up using your own keys, for partial credit.)
Follow the outline below in preparing your answer, i.e., first provide the answers to the questions (1)-(4), and then provide a detailed explanation, including pseudocodes, for each.
(1) Selected anagram index: (2) Public key:
(3) Private key:
(4) Decoded message:
Detailed Explanation for (1): Detailed Explanation for (2): Detailed Explanation for (3): Detailed Explanation for (4):
10038694
Page 7
Question 6: Hash Hash ………………………………………..(17 points) In this question, you will analyze the empirical and theoretical collision probability for a new hash function.
The hash function h maps binary vectors of dimesion m to binary vectors of dimension n, where m > n, with the help of an n ⇥ m matrix H with binary elements that are generated randomly. More specifically, given the matrix H , the hash function h : {0, 1}m ! {0, 1}n provides the following hash value for a key x 2 {0, 1}m :
h(x) = Hx mod 2
where the mod operator is applied element-wise (to the obtained vector Hx).
For instance, if m = 3, n = 2, H is the matrix consisting of all ones, x is the vector of all ones, then the obtained vector Hx will be the vector of all threes, and when the element-wise mod 2 is applied, the two-dimensional vector h(x) will be obtained as the vector of all ones.
(a) (5 points) Show your understanding of the described hash function, h, by constructing the following example:
• Letn=3.
• Construct the hash key x as follows:
– Take your first name as a string; replicating it if it has 4 letters, so that the obtained string has at least 5 letters, e.g., “merve”, “juyoung”, “berkberk”, “nedaneda”, “yuyuyu”.
– Letting ci be the ith letter in the obtained string, set the ith element of the x vector as 1 if ci 2 {a,b,c,. . .,m}, and 0 otherwise. (For instance, “merve” would yield x = (1, 1, 0, 0, 1).)
• Set numpy’s random number generator’s seed to the last 4 digits of your student number, and generate a random binary H matrix of appropriate dimension.
Find h(x). Show all your work.
nbcdefghijklm
0，1，1.0 lhaohaoil.li
9478
迨咒⻔门
(1) String obtained from the first name:
(2) x : (3) Seed: (4) H: (5) h(x):
从6⼈人6 ⼆二了了刈
H x mod2 1.1.17
Detailed Explanation for (5):
Page 8
(b) (3 points) Prove that the collision probability for h is 1 , i.e., given two di↵erent vectors x0,x00 2 m 0 00 1 2n
{0,1} ,wehavePr{h(x)=h(x)}=2n.
HINT: The proof is very similar to what we have done in class. This time while generating the random H matrix, without loss of generality, assume that all the columns of H are fixed and only one is to be randomly generated.
(c) (9 points) Compare the theoretical and empirical collision probabilities as follows:
• At the beginning of your code, only once, set the numpy’s random number generator’s seed to the
last 4 digits of your student number.
• Consider the n options as {3,4,…,15}.
• Letm=2n.
• For each (n, m) option, do the followings:
– Generate a random H matrix of appropriate size.
– Randomly generate N = 10000 pairs of x0 and x00 such that x0 6= x00
(For numpy arrays, you can use the function numpy.array equal(x’,x’’))
– Count how many pairs have a collision, i.e., h(x0) = h(x00)
(numpy.matmul(H,x)function could be useful for matrix and vector multiplication
– Record the empirical collision probability for this (n, m) option as
Proof:
(the counter value from the previous step)/N – Record the theoretical collision probability for this (n, m) option as 1
2n
• Plot on the same graph the empirical and theoretical collision probabilities for di↵erent values of n.
(Let x-axis and y-axis correspond to the n and probability values, respectively.)
In addition to submitting your final code as a single script named hash utorid.py and the generated plot as a pdf or png in Quercus, provide a pseudocode and a manually drawn version of the plot. Explain what you observe from the plot.
Pseudocode: Plot:
Plot observation:
Page 9
Question 7: Not Too Complex …………………………………(10 points)
Let v be an n-dimensional vector. For convenience, we will start the vector indices at 1, and use the following notation: v[i : j] denotes the subvector of v obtained by keeping the elements at indices i, i + 1, . . . , j. Note that v> denotes the transpose of the vector v, making it a row vector.
1 2 3 4 5 6 7
function WeirdNorm(v): n = dimension of v
if n = 1: return v>v
else:
return v>v + WeirdNorm(v[1:n-1])
Calculate the On complexity of the WeirdNorm function. Show your work, i.e., count the number of addition (A) and multiplication (M) operations. At the end, you may use A = M = 1.
(Note that the question asks for On, not O(n). Beware that a simple guess will not get any partial credit.)
Also do the same analysis in the following special case: Assume that the input vector v has all the same elements, e.g., it is the vector of all fives.
(1) On (general case): (2) On (special case):
Detailed Explanation for (1): Detailed Explanation for (2):
Page 10
Question 8: Too Complex …………………………………….. (10 points)
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21
LetAbeann⇥nmatrix. LDUdecompositionfindsn⇥nmatricesL,D,U suchthatA=LDU> where • L is lower triangular with unit diagonal elements,
• D is a diagonal matrix (i.e., a matrix in which the entries outside the main diagonal are all zero),
• U is upper triangular with unit diagonal elements.
LDU decomposition algorithm (pseudocode) is provided below, where the matrix/vector indices start at 1 and the following notation is used:
A[i : j,k : l] denotes a submatrix of A obtained by keeping i,i+1,…,j rows and k,k+1,…,l columns of A, while single elements of matrices/vectors are shown using subscripts.
function LDM(A):
n = dimension of A
d = n ⇥ 1 zero vector
v = n ⇥ 1 zero vector
L = n ⇥ n identity matrix U = n ⇥ n identity matrix D = n ⇥ n zero matrix
for i = 1,2,. . .,j-1:
Uji =vi /Dii is
ifj=1:
L[j:n,j] = A(j:n,j) / vj
II niltjtytcj ly
剖 个州升 ⼀一闪刋个M
for j = 1,2,…,n:
v[1:j] = ForwardSubstitution(L[1:j,1:j],A[1:j,j]) dj=vj
Djj=dj
ifj>1:
n
2
else:
L[j:n,j] = (A(j:n,j) – L(j:n,1:j-1) ⇤ v[1:j-1]) / vj
return (L,D,U)
卡 琯孙 华 7
ii
Calculate the On complexity of the LDU decomposition. Show your work, i.e., count the number of addition (A) and multiplication (M) operations. At the end, you may use A = M = 1. (You can use the known complexity for the ForwardSubstitution, no need to re-calculate it.)
(Note that the question asks for On, not O(n). Beware that a simple guess will not get any partial credit.)
(1) On :
Detailed Explanation for (1):
Page 11
冰 n则
M
in