ORIE5270 – Homework 4
Due February 22nd, 2019 at 1:25pm
You are not allowed to collaborate with your classmates. Submit this assignment by pushing a folder HW4 to your ORIE5270 repository on cornell’s github with your solutions as well as a solution file in pdf format containing your repo url to Blackboard. Make sure all your code are readable. You should also tell us how to run your code in your solution file.
Problem 1
Problem 2
Problem 3
(Test of NameHeap) Modify your NameHeap class last homework so that if the NameHeap is empty, the function smallestName() and deleteSmallestName() will print out a message
There is no one in the Heap.
Now write a python file NameHeapTests.py to test each function in your NameHeap using the python module unittest or nose. Explain how you test each function (you can include your code with enough comments so you don’t need to repeat your work) and how other people can run your test in your solution file. You repo should contain NameHeapTests.py.
(Subnormal numbers) Assuming you are only dealing with IEEE754 floating point num- ber with double precision (binary64) in this problem.
(1) What is a subnormal number? Give an example of a subnormal number (don’t use the one, 2−1022−50, in the class).
(2) Write a routine detectSubnormalNumber.py that outputs true if a given float is a subnormal number and false otherwise. Write a test file TestDetectSubnormalNumber.py to test detectSubnormalNumber.py with examples of your own. The solution file should contain explanations of why your routine works, and your tests cases.
(Quadratic Formula) Consider solving the quadratic equation
x(x − 2b) = c (1)
for some constants b, c ∈ R and c ≥ 0, which ensures the solutions are real.
(1) Using the quadratic formula, for a given input of b, write a python file qesolution.py
that outputs a pair of solutions x that satisfies the above equation. Then write a test file TestQesolution.py to test your solution are accurate for various but not extreme b, c. To test the accuracy of the two roots, calculate the theoretical value of : x∗1 + x∗2 and x∗1x∗2 where x∗1, x∗2 are solution to (1) and test against those values in terms of relative error. Make sure your accuracy is at least 10−12.
(2) Add unit tests to your TestQesolution.py for scenarios when b is large in magni- tude and when c is small (so that they fail your function qesolution.py). What happens to the relative error and why? Write your solution to the two questions and your choice of b and c in the solution file. (Note: don’t worry about when b2/c > 252)
(3) There is more than one way to write the quadratic formula. Multiply the numerator and denominator by the conjugate to move the square root term to the denominator.
Write a new python file qesolutionRevise.py for solving the quadratic equa- tion that selectively chooses the more numerically stable formula depending on the right situation. Explain why your code works in your solution file. Your qesolutionRevise.py should also pass your previous tests in TestQesolution.py.
(Matrix-vector Product) Suppose you want to know the complexity of the following matrix-vector product using numpy:
import numpy a s np
Problem 4
1
2
def matrixVectproduct (A, b ) : return A∗b
Of course, you know for a matrix A ∈ Rn×n and b ∈ Rn, computing the matrix-vector product Ab should take no more than n2 number of arithmetic operations. However, since numpy matrix-vector product A*b is a black box to you, you are not perfectly sure about your answer O(n2). Can you use a plot to see the complexity of matrix-vector product? Write a python script MatrixVectorProductComplexity.py for the plot. Put your plot in your solution file, explain how you make the plot, and the complexity of the matrix-vector product reflected in the plot.