Final Exam

CS 5351/CS 4365, Fall 2013

Name: ___________________________________________________________

1. What is the main problem of interval computations? Why is this problem useful in practice?

2-5. We want to estimate the range of a function f(x) = x −
2x^{2} on the interval [0,0.4]. Do the following:

- find the exact range by using calculus;
- estimate the range by applying naive (straightforward) interval computations to the original interval;
- 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;
- use bisection and apply mean value form (with checking monotonicity first) to both sub-intervals.

6-7. In class, we studied two linearization algorithms:

- Algorithm 1 that uses partial derivatives, and
- Algorithm 2 which does not.

8. Use calculus to find the range of a function f(x_{1},
x_{2}) = (x_{1})^{2} + x_{1}
* x_{2} − (1/2) * (x_{2})^{2} +
x_{2} when x_{1} is in the interval [−1, 1],
and x_{2} is in the interval [−2, 2]. *For extra
credit:* use naive interval computations to estimate this
range.

9. Use the interval-based optimization algorithm to locate the
maximum of the function f(x) = x − 2x^{2} on the
interval [0, 0.8]. 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.

10-11. Use the constraints method to solve the following two problems:

- find x
_{1}from the interval [1, 2] and x_{2}from the interval [−5, −1] which satisfy the system of equations x_{1}+ 2x_{2}= 1 and x_{1}* x_{2}= −3; - find x
_{1}from the interval [1, 2] and x_{2}from the interval [−5, −1] which satisfy the system of equations x_{1}+ 2x_{2}= 1 and x_{1}* x_{2}= 0.

12. If we use the simplest "and"- and "or"-operations, and our degrees of belief in A, B, and C are, correspondingly, 0.5, 0.6, and 0.7, what is our degree of belief in (A \/ B) & C?

13. For a membership function μ(x) = 1 − |1 − x|, what are the α-cuts corresponding to α = 0.6? to α = 0.7?

14-15. 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 − |1 − 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.

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

17. Write down a Java method which computes the values

18. Suppose that we have three alternatives, for which the gains are in the intervals [0, 5], [−4, −1], and [−3, 10].

- Is there an alternative which is guaranteed to be optimal (i.e., for which the gain is the largest)?
- List all alternatives which can be optimal.
- Which alternative(s) should we select if we use Hurwicz optimism-pessimism criterion with α = 0, 0.5, and 1.

19. Write down:

- an expression for which an optimizing compiler improves the estimates provided by straightforward interval computations, and
- an expression for which an optimizing compiler worsens improves the estimates provided by straightforward interval computations.

20. If we use 2-digit decimal numbers, what will be the result of multiplying the intervals [0.30, 0.65] and [0.77, 1.30]?

21. Briefly describe your project for this class.

22. Briefly describe someone else's project for this class.