Analysis of Algorithms : An Active Learning Approach

242 OTHER ALGORITHMIC TECHNIQUES

shape. We would just generate random points in a surrounding square and

determine the ratio that fall inside the shape. The ratio of

is the same as the ratio of

Monte Carlo Integration^3

You may recall that for a continuous function f, the area under the curve for f is

the integral of the function. For some functions, it is difficult or impossible to

determine this integral, but we can get it through our dart technique. For the

purposes of illustration, we will restrict ourselves to that portion of f bounded

by the x and y axes and the lines x = 1 and y = 1 (see Fig. 9.4). You should be

able to generalize this to any size bounding box.

We randomly throw darts at the square and count how many wind up

below the curve. The number below the curve divided by the number thrown

will give us an approximation of the area under the curve. As in past cases, the

more darts that are thrown, the more accurate the approximation. The follow-

ing algorithm achieves this:

Integrate ( f, dartCount )

f is the function to be integrated

dartCount is the number of darts to throw

(^3) It is unfortunate that this is the traditional name for this technique because it is unre-
lated to the Monte Carlo techniques to be discussed later.
darts inside the shape
-------------------------------------------------total darts thrown-
area of the shape
area of the square

y = 1
x = 1
■FIGURE 9.4
A function
bounded by the
x axis, the y axis,
and the lines x = 1
andy = 1