Final Exam for the course

CS 5391/CS 6391, Fall 2015

Name: ___________________________________________________________

General comments:

- If you need extra sheets of paper, please place your name on all of them.
- 10 pages for handwritten notes allowed.

1 (30 points) We want to estimate the range of a function (1 + 2 * x) * (2 − x) on the interval [−2, 0]. Do the following:

1a. Find the exact range by using calculus.

1b. Estimate the range by applying naive (straightforward) interval computations to the original interval.

1c. Use bisection and check monotonicity of the function on each of the sub-intervals, applying naive interval computations only if the function is not monotonic.

1d. Use bisection and apply the centered form (with checking monotonicity first) to both sub-intervals.

1e. Apply affine arithmetic to estimate the desired range.

1f. Use two linearlization algorithms that we studied (Algorithm 1 that use partial derivatives and Algorithm 2 that does not use partial derivatives) to estimate this range.

2 (10 points) Find the range of a function f(x_{1},
x_{2}) = (x_{1})^{2} − x_{1}
* x_{2} − x_{2}^{2} −
x_{2} when x_{1} is in the interval [−1, 1],
and x_{2} is in the interval [−2, 2]:

2a. by using calculus

2b. by using naive interval computations.

3 (5 points) Use the interval-based optimization algorithm to locate the
maximum of the function f(x) = (1 + 2 * x) * (2 −
x) on the interval [−0.8, 0]. Divide this interval into
two, then divide each of the remaining intervals into two again,
etc. Stop when you get intervals of width 0.1.

4 (10 points) Use the constraints method to solve the following two
problems:

4a. Find x_{1} and x_{2}, both from
the interval [0, 1], that satisfy the system of equations
x_{1} + x_{2} = 1 and

x_{1} *
x_{2} = 0.16.

4b. Find x_{1} and x_{2},
both from the interval [0, 1], that satisfy the system of equations
x_{1} + x_{2} = 1 and

x_{1} *
x_{2} = 0.7.

5 (15 points)

5a. If use the simplest "and"- and "or"-operations min and max, and our degrees of belief in A, B, and C are, correspondingly, 0.3, 0.8, and 0.5, what is our degree of belief in (A \/ B) & C?

5b. For a membership function μ(x) = max(0, 1 − |2 − x|, 0), what are the α-cuts corresponding to α = 0.5? to α = 0.9?

5c. Let us assume that the quantity x is described by the membership function μ(x) = 1 − |x|, and the quantity y is described by the membership function μ(y) = 1 − |2 − y|. Use the values α = 0.2, 0.4, 0.6, 0.8, and 1.0 to form membership functions for z = x + y and t = x * y.

6 (5 points) Follow the first three steps of bisection to locate the square
root of 11, i.e., the solution to the equation x^{2} −
11 = 0 on the interval [0, 4].

7 (5 points) Write down a Java method that, given a function f,
values x_{1}, ..., x_{n}, and a number h,
computes the sum (c_{1})^{2} + ... +
(c_{n})^{2}, where
c_{i} = (f(x_{1}, ..., x_{i − 1},
x_{i} + h, x_{i + 1}, ..., x_{n}) −
f(x_{1}, ..., x_{i − 1}, x_{i},
x_{i + 1}, ..., x_{n})) / h.

8 (15 points) Suppose that we have three alternatives, for which the gains are
in the intervals [0, 100], [−80, −20], and [−60, 200].

8a. Is there an alternative which is guaranteed to be optimal (i.e., for which the gain is the largest)?

8b. List all alternatives which can be optimal.

8c. Which alternative(s) should we select if we use Hurwicz optimism-pessimism criterion with α = 0, 0.5, and 1.

9 (10 points)

9a. Write down an expression for which an optimizing compiler improves the estimates provided by straightforward interval computations. This expression should be different from the examples that I gave; minor difference is OK.

9b. Write down an expression for which an optimizing compiler worsens improves the estimates provided by straightforward interval computations. This expression should be different from the examples that I gave; minor difference is OK.

10 (5 points) If we use 2-digit decimal numbers, and what to get guaranteed
bounds, what will be the result of
multiplying the intervals [0.13, 0.54] and [0.67, 1.30]?