Problem Statement |
| | We want to find the location of a local maximum in an unknown function. y = f(x) is
a continuous real-valued function defined on the real numbers.
We already have a number of data pairs, (xi, yi), and we need to find
a small interval on the x axis that is guaranteed to contain at least one local (or global)
maximum.
But taking a sample from this function
is quite expensive so we are only allowed to take N samples. Our problem is to
choose them in such a way as to minimize the size of the interval that we
determine.
The sampling will be done sequentially: we choose a value of x and find the
corresponding y value, f(x). We repeat this process N times, choosing the x value based on
all the data collected so far.
We are willing
to assume that no two y values will be exactly equal to each other.
Create a class LocalMax that contains a method length that is given N, the
number of samples we can take, and double[]s xData and yData
(the existing data pairs). It will return the worst case length for our interval
around a local maximum using optimal sampling. If it is not possible to make such
a guarantee, it returns -1.0.
|
| |
Definition |
| | | Class: | LocalMax | | Method: | length | | Parameters: | int, double[], double[] | | Returns: | double | | Method signature: | double length(int N, double[] xData, double[] yData) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The returned value must be accurate to within a relative or absolute value of 1E-9 |
| |
Constraints |
| - | N will be between 0 and 25 inclusive. |
| - | xData will contain between 1 and 50 elements inclulsive. |
| - | yData will contain the same number of elements as xData. |
| - | The elements of yData will be distinct. |
| - | The elements of xData will be distinct. |
| - | Each element of xData and yData will be greater than 0.0 and less than 10000.0. |
| |
Examples |
| 0) | |
| | | Returns: -1.0 | |
From the data we already have we cannot guarantee that this function even
has a local maximum -- it might be monotonically increasing.
|
|
|
| 1) | |
| | | Returns: 2.0 | |
We know that there is a local maximum between x=3 and x=5. |
|
|
| 2) | |
| | | Returns: 2.0 | |
Here is one way (there are others) get an interval of length 2 or less
with just two additional samples. Take the
first sample at x=6.5. The worst case is that the corresponding
y value is less than 923.2. In that case we know that the interval
(3,6.5) contains a local maximum, and that the y value at x=5 is greater than
either endpoint y value. Take the second sample at x=4.7. In the worst case
the corresponding value of y will be bigger than 923.2, in which case we
could conclude that there is a local max somewhere in the interval (3,5).
|
|
|
| 3) | |
| | | Returns: 1.0 | |
If we take a sample at x=4.0+epsilon, for some tiny epsilon, then the
worst case would be that the corresponding y value would be smaller than
53. In that case the interval between 3.0 and 4.0+epsilon would contain
a local maximum. So by choosing epsilon arbitrarily small, we get an
interval whose length is (arbitrarily close to) 1.0.
|
|
|
| 4) | |
| | 3 | {1,4.3,7.2,95.4,534.0} | {72, 83, 19, 25.3, 624.0} |
| Returns: 1.4500000000000002 | |
|