Data Processing under Security and Privacy
Homeworks for the course
CS 4365/CS 5354, Summer 2016

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 x3 − a when a = 2 and x = 1.

5. (Due June 9) Use Newton's method to solve the following system of non-linear equations: x1 * x2 = 2, x12 − x22 = −3. One iteration is good enough, two iterations for extra credit.

7. (Due June 30) Find the point closest the origin on the line x1 + x2 = 1. In other words, find the values x1 and x2 for which the sum (x1)2 + (x2)2 attains the smallest possible value under the constraint x1 + x2 = 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 = (c1)2 * (σ1)2 + ... + (cn)2 * (σn)2 is the smallest possible under the constraint ρ(x) * 2n * σ1 * ... * σn = k. Here, ci is the partial derivative of the desired statistical characteristic C(x1, ..., xn) with respect to the i-th variable xi.

9. (Due July 5, 2016) Use linearization techniques to estimate the range of the function f(x1, x2) = (x1)2 + 4 * x1 * x2 + 4 * (x2)2 when x1 is in the interval [−1.2, −0.8] and x2 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(x1, ..., xn) 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:

The algorithm is straightforward:

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 52016 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 n2 = n * n mod m, n4 = n2 * n2 mod m, n8 = n4 * n4 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 711 mod 9. In binary, 11 is 10112, i.e., 11 = 8 + 2 + 1. Thus, 711 = 78 * 72 * 71. Following the above algorithm, we first compute:

After that, we compute 711 = 78 * 72 * 71 = 4 * 4 * 7 mod 9. Here, 4 * 4 = 16 = 7 mod 9, so (4 * 4) * 7 = 7 * 7 = 49 = 4 mod 9. So, the answer is that 711 mod 9 = 4.

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:

The last remainder is 1, so 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:

Here, 46 * 50 − 19 * 121 = 1, so 46 * 50 = 1 mod 121. The answer is d = 46.

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:

Reminder: in preparation to the RSA encoding: Once the public code is selected, the original message m is replaced by the encoded message which is computed as c = me mod n. On receiving the encoded message c, the recipient (who knows the secret code d) can decode the secret message as m = cd mod n.

20. (Due July 20, 2016) Use the Chinese remainder theorem algorithm to find a number n for which: