Test 2 for CS 5383, July 18, 2006

Name: ___________________________________________________________________

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

1-7. Probabilistic approach to trust

1. If events A and B are independent, with Prob(A)=0.7 and Prob(B)=0.8, what is the probability of A & B? what is the probability of A \/ B? Explain your answers.

2. If a directly trusts b with probability 0.9, a trusts c with probability 0.8, and c trusts b with the probability 0.7, what is the resulting probability with which a trusts b?

3. Describe the basic Monte-Carlo algorithm for computing the probability of trust.

4. How can we use a standard random number generator - that generates real numbers uniformly distributed on the interval [0,1] - to simulate an even occurring with a given probability p0? Where is this idea used in the basic Monte-Carlo algorithm for computing the probability of trust?

5. Why is the basic Monte-Carlo algorithm not efficient in case of almost perfect trusts -- when the original trust probabilities are close to 1? Hint: recall how the accuracy of the Monte-Carlo method depends on the number of simulations.

6-7. If a directly trusts b with probability 0.99, a trusts c with probability 0.98, and c trusts b with the probability 0.97, what is the resulting probability with which a trusts b? Give a direct answer, and then use the scaling algorithm to provide an answer.

8-10. Constraints

8. Use the constraints and intervals algorithm to show that the line y=x-x^2 has no intersection with the line y=1 when x is in [0,1].

9-10. Use the constraints and intervals algorithm to find the solution to the system of equations y=x-x^2 and y=0.09 when is in [0,1]. It is sufficient to perform the first few iterations, with some bisection.