1. (Due June 8) Similarly to how we used Newton's method to design algorithms for computing square root and cubic root, design an algorithm for computing the fourth order root.
2. (Due June 10) Write a method (program) for solving a system of linear equations. Turn in a printout of the code and a printout of an example on which you tested your method.
3. (Due June 8) Use the algorithm for computing 1/b that we had in class (and that is implemented in the computers) to perform the few first steps of computing 1/1.25.
4. (Due June 8) Use numerical differentiation to compute the derivative of the function x^{3} − a when a = 2 and x = 1.
5. (Due June 9) Use Newton's method to solve the following system of non-linear equations: x_{1} * x_{2} = 2, x_{1}^{2} − x_{2}^{2} = −3. One iteration is good enough, two iterations for extra credit.
7. (Due June 30) Find the point closest the origin on the line x_{1} + x_{2} = 1. In other words, find the values x_{1} and x_{2} for which the sum (x_{1})^{2} + (x_{2})^{2} attains the smallest possible value under the constraint x_{1} + x_{2} = 1.
8. (Due July 5) Similarly to what we did in class for selecting the optimal box for interval privacy protection, find the standard deviations σ_{i} that describe the optimal probabilistic disruption. In precise terms, find the values σ_{1}, ..., σ_{n} for which the sum σ^{2} = (c_{1})^{2} * (σ_{1})^{2} + ... + (c_{n})^{2} * (σ_{n})^{2} is the smallest possible under the constraint ρ(x) * 2^{n} * σ_{1} * ... * σ_{n} = k. Here, c_{i} is the partial derivative of the desired statistical characteristic C(x_{1}, ..., x_{n}) with respect to the i-th variable x_{i}.
9. (Due July 5, 2016) Use linearization techniques to estimate the range of the function f(x1, x_{2}) = (x_{1})^{2} + 4 * x_{1} * x_{2} + 4 * (x_{2})^{2} when x_{1} is in the interval [−1.2, −0.8] and x_{2} is in the interval [0.9, 1.1].
10. (Due July 5, 2016) Use naive (straightforward) interval computations to estimate the range from Problem 9.
11. (Due July 6, 2016) Write a program that, given a function f(x_{1}, ..., x_{n}) and n intervals, uses linearization techniques to estimate the range of the given function on the given intervals.
12. (Due July 11, 2016) Use the algorithm that we discussed in class to eliminate outliers from the following database:
Comment: In this homeworks, we selected 2-sigma intervals, but we could select 3-sigma, 6-sigma, etc.
13. (Due July 11, 2016) Use the general formula to find the sizes of the cell that provides the smallest possible inaccuracy in computing the covariance between height and weight; assume that:
14. (Due July 14, 2016) Use the general algorithm to find the sizes of the call that provides the smallest possible inaccuracy in computing the covariance between height and weight; assume that:
15. (Due July 14, 2016) How much privacy do we lose if someone detects the second digit x in the height 1xy? the third digit y? Assume that the height is between 145 and 185 cm.
16. (Due July 15, 2016) Use the efficient raising-to-the-power algorithm that we learned in class to compute 5^{2016} mod 11.
Reminder: To raise a number n to the power p mod m, we first represent p in the binary code, as the sum of powers of two. Then, we compute n^{2} = n * n mod m, n^{4} = n^{2} * n^{2} mod m, n^{8} = n^{4} * n^{4} mod m, until we get all needed powers of two. Then, we multiply the resulting powers of two mod m.
Example: suppose that we want co compute 7^{11} mod 9. In binary, 11 is 1011_{2}, i.e., 11 = 8 + 2 + 1. Thus, 7^{11} = 7^{8} * 7^{2} * 7^{1}. Following the above algorithm, we first compute:
17. (Due July 15, 2016) Use Euclid's algorithm to compute the greatest common divisor gcd(2016, 361).
Reminder: Euclid's algorithm means that to compute gcd(a, b), where a > b, we repeatedly take into account that gcd(a, b) = gcd(b, a % b). We stop when we get remainder 0, in which case the last non-zero number id the desired gcd.
Example:
18. (Due July 18, 2016) Use Euclid's algorithm to find a number d for which d * 50 mod 121 = 1.
Solution: First, we use Euclid's algorithm to check that indeed gcd(121, 50) = 1:
Next, for each of the remainders 21, 8, etc., we represent it as a linear combination of the original numbers 121 and 50, until we get such a representation for remainder 1:
19. (Due July 19, 2016) Show, step-by-step, how the RSA algorithm works, on the following example. We select p = 5, q = 7, and e = 11, and want to encode and decode the message m = 12. What you need to do:
20. (Due July 20, 2016) Use the Chinese remainder theorem algorithm to find a number n for which: