When dokumenting the solutions to the exercises use a word processor and do not write by hand. Using a word processor saves time both for you and certainly for me, that have to check your solutions.
Exercise set 7: due in written by March 21.
1. What effect on the RandQS would it have if in the choice of the dividing element, the middle of three random elements were choosen?
2. What is the probability to find a min-cut for the graph in Figure 1.1 (Motwani & Raghavan) in one application of the min-cut algorithm? The question may be answered either theoretically or by experimenting. Compare this value to the lower bound 2/[n(n-1)]. How many applications do you need for the probability to find a min-cut to be at least 0.95 for each of these estimates?
Exercise set 6: due in written by March 7.
1. Implement the Simulation Net model of Set 5, ex. 2 in SimNet and perform experiments to answer the questions asked in the Introduction.
Exercise set 5: due in written by February 21.
1. Change the program used to solve set 4, problem 3 so that estimates to all minima found are printed. Do this by recognizing if solutions are "close enough" to represent the same minimum and by keeping only the best representative for each minumum during the computation. Also estimate and report the relative size of the basin of each minimum found. (The number of points leading to it divided by the total number of points). Try to analyze if there is a fifth minimum with a value about 99 near the point (1.2,-0.2).
2. Use Simulation Nets to model the problem described in Section 1.4
Exercise set 4: due in written by February 14.
1. Estimate the ratio between the volume of a hypersphere and the volume of the smallest box containing it for dimensions n=2,...,10. Plot the result with the ratio on the y-axes and n on the x-axes. What is the result for n=1?
2. Implement Unirandi. Test it on the function in 3. by starting it from (1,1) using h0=0.1, hm=0.001 and using random numbers by initializing combtaus as in Set2. Check the working by printing out the successive points (x1,x2,f(x1,x2),h).
3. Estimate the global minimum (x, f(x)) of the function (GOLDPR)
f(x1,x2) = [1 + (x1+x2+1)2 (19-14x1+3x12-14x2+6x1x2+3x22)]* [30 + (2x1-3x2)2 (18-32x1+12x12+48x2-36x1x2+27x22)]in [-2,2]2 by starting Unirandi from 100 uniformly sampled points. Repeat this with with different seeds. How many minima do you think there are? (f(1,1)=1876).
Exercise set 3: due in written by February 7.
1. For exercise 3 in set 2 use the theory to reason about how many trials you will need.
2. For the illustrative function used by Halton & Handscomb use n=100 and compare the results for Hit-or-miss MC, Crude MC, and Antithetic variates using the estimator 0.5[f(x)+f(1-x)]. Use your combtaus generator.
3. For the same function as in exercise 2 what results do you obtain for Hit-or-miss MC and Crude MC when using the quasi random numbers phi2(i), phi3(i) and phi2(i), i = 0,...,99 instead of using uniform random numbers?
Exercise set 2: due in written by January 31.
1. Implement the combtaus generator. Give the 10 first random numbers produced by the generator when Mask1 and Mask2 are used as seeds.
2. Implement Leva's RANDN(seed1,seed2) by using combtaus for uniform random numbers. Give the 10 first numbers produced by the generator when Mask1 and Mask2 are used as seeds.
3. Use Crude MC to compute the integral below with two correct figures by using a successively increasing number of trials. How many trials will you need?
( 1
/ (ex-1)/(e-1)dx
) 0
(Crude M(onte)C(arlo) means taking averages of integrand values)
Exercise set 1: due in written by January 24.
1. Estimate pi by performing a Buffon needle experiment with N=100.
2. For the middle-square method determine all cycles for the base 10 and number of digits 2.
3. Determine all cycles of
xi = 21xi-1 + 1 (mod 102).
4. Determine the cycles of
xi = aix0 (mod 102)
for a=2,3,...,7 and x0=a.
5. For
bi = a1bi-1 + a2bi-2 + a3bi-3 + bi-4 (mod 2)
determine ai so that the period is maximal (15). For this generator give a sequence of 15 4-bit "random numbers".