## 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.