Final exam for CS 5383, July 25, 2006

Name: ___________________________________________________________________

Please use as many sheets of paper as you need; do not forget to place your name on all these sheets.

1-2. Security and Privacy

1. One of the methods proposed to preserve privacy in statistical databases is to only allow queries that combine at least m records (where m is a given threshold). Illustrate the limitations of this method on the following example of a database that contains the body temperature of several patients; in this example, m = 5.

Based on this information, find the temperature of patient No. 6. What is your conclusion: is this an efficient way to protect privacy?

2. Another method of protecting privacy is adding a random error to the answer. Explain, in detail, what are the limitations of this method, i.e., how exactly we can reconstruct the original values that we are supposed to be protecting. How can we avoid the limitations of these privacy protection methods?

3-10. Uncertainty

3-5. For the case when the data processing algorithm is f(x1,x2) = 1/x1-x2, the measured values are X1 = 1.0 and X2 = 3.0, and the upper bounds on the measurement errors are D1 = D2 = 0.1, find the bound on D by using the following three methods:

3. use monotonicity to find the exact range and then, the value D;

4. use analytical differentiation;

5. use numerical differentiation.

6. Formulate the general problem of estimating the the standard deviation S on the approximation error of result of data processing: what is known, and what we need to compute. Explain what is a standard deviation (i.e., how it is defined in precise terms).

7. Describe, in detail, Monte-Carlo algorithm for computing the standard deviation S of the result of data processing.

8-9. For the case when the data processing algorithm is f(x1,x2) = 1/x1 - x2, the measured values are X1 = 1.0 and X2 = 3.0, and the standard deviations of the measurement errors are s1 = 0.04, s2 = 0.03, find the standard deviation s of y - Y by using the following two methods:

8. use analytical differentiation;

9. use numerical differentiation.

10. Explain what are fuzzy numbers. For the case when the uncertainty in x1 is described by a triangular number with a center 1.0 and base [0.9,1.1], and the uncertainty in x2 is described by a triangular number with a center 3.0 and base [2.9,3.1], describe the fuzzy number corresponding to y = 1/x1 - x2.

11-17. Probabilistic approach to trust

11. If events A and B are independent, with Prob(A)=0.5 and Prob(B)=0.6, what is the probability of A \/ B? Explain, in detail, the formula that you are using.

12. Let a trust c with probability 0.8, a trust d with probability 0.9, c trusts b with probability 0.7, and d trusts b with the probability 0.9. What is the resulting probability with which a trusts b? Explain your formula step by step.

13-14. Describe the basic Monte-Carlo algorithm for computing the probability of trust, including the use of the standard random number generator (RNG). How is this use different from the use of RNG to estimate uncertainty?

15. What is the accuracy of the basic Monte-Carlo algorithm for estimating trust? Based on this accuracy, how many simulations do we need to make to estimate the trust with accuracy 1%? 0.1%?

16-17. Let a trust c with probability 0.98, a trust d with probability 0.99, c trusts b with probability 0.97, and d trusts b with the probability 0.99. What is the resulting probability with which a trusts b? Give a direct answer, and then use the scaling algorithm to provide an answer.

18-20. Constraints

18. Use the constraints and intervals algorithm to show that the system of equations x*y=6 and x+y=10 has no solution when x and y are in the interval [0,5].

19-20. Use the constraints and intervals algorithm to find the solution to the system of equations x*y=6 and x+y=5 when both x and y are in the interval [0,5]. Hint: after a few iterations, we must use bisection.