Probabilistic Algorithms: Quiz 1, Date 28.2.2001

1. Consider the mixed congruential pseudo random generator

          xn = axn-1 + c (mod m)
   

   a) What is the maximal period of a generator of this type? b) Give a sufficient condition for maximal period. c) Give all the cycles of the generator with a=3, c=7 and m=10.

2. What is the difference between pseudo random numbers and quasi random numbers? Give the first 10 numbers of the van der Corput quasi random number sequence with base 3. Write them in decimal rational form with the common denominator 9.

3. a) Give the expression for a Crude Monte Carlo estimate of the integral of the function f(x) over the region A. The region A is inside the two-dimansional box H with the length of its edges equal e₁ and e₂. The estimate should be based on N points sampled at random in H of which the points y₁, y₂,..., y_n were found to be inside A. b) What is the convergence rate of the estimate as N increases? c) Let G be another box containing A but with twice as long edges. Using this box instead of H in your estimate, how many points should you sample in order to obtain the same accuracy as with H?

4. Given the 10 points x₁, ..., x₁₀ = 1,2,5,7,8,10,13,14,15,16 with function values f(x_i) = 3,7,8,6,5,6,6,5,6,7 one wants to find the graph minima when using the topographical global optimization technique with k=2 (two nearest neighbors). Determine the distance matrix and the 2-nearest neighbors table and show how the graph minima can be found.

5. Derive the Simulation Net describing the following simple public hospital system.
   Patients arrive at the hospital for medical checks with interarrival times having the negative exponential distribution with mean 2h. They will first be interviewed by a nurse (5-10 min) and thereafter the medical check will be made by the doctor and takes 10-15 min. The patient then waits for 10-15 min and then with the probability 1/2 either leaves or will undergo a small operation (15-25 min) performed by the doctor assisted by a nurse and then leave. There is one doctor and two nurses at the hospital. (Hint: The leaving or waiting with the probability 1/2 could be modeled by using a place, which half of the time is empty and half of the time contains a token.)

Write structuredly, clearly, legibly, and briefly!