Homeworks for the course

CS 5351/CS 4365, Fall 2013

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

- find the exact range by using calculus;
- estimate the range by applying naive (straightforward) interval computations to the original interval;
- first, use naive interval computations to check monotonicity, and, if monotonicity is confirmed, use it to get a more accurate estimate for the range.

2. (Due September 9) We want to estimate the range of a function
f(x_{1}, x_{2}) = (x_{1})^{2} −
x_{1} * x_{2} + 2 * (x_{2})^{2}
+ x_{2} when x_{1} is in the interval [−1, 1], and
x_{2} is in the interval [−2, 3].

- find the exact range by using calculus;
- estimate the range by applying naive (straightforward) interval computations to the original intervals

1-2. A sample solution to Problems 1 and 2

3. (Due September 11) Write a program that implements all operations of interval arithmetic: addition, subtraction, multiplication, 1/x, and division. Submit printouts of the code and of the test results, be prepared to show how the program works if needed.

Comments:

- the range of 1/x is only bounded when the set of possible values of x does not contain 0; thus, the inverse interval 1/[a,b] is only defined when the interval [a,b] does not contain 0;
- the main need for interval arithmetic operations comes from naive interval computations, where the result of one operation are used as inputs for another interval arithmetic operation; in view of this, please program interval arithmetic operations so that they return the interval, not just print its endpoints; in an object-oriented programming language like Java, the most convenient way is to return an interval as an object;
- endpoints come from measurements; we saw many examples in class when endpoints are not integers; please make sure that your operations are defined for real numbers, not just for intervals.

4. A sample solution to Problem 4

Comment: Please *do not* change the expression when using
interval computations; as we saw in class, an equivalent
transformation can change the resulting enclosure.

5. (Due September 18) Use mean value method to find an enclosure
for the range of a function f(x) = 2x − 3x^{2} on the
interval [0,0.8].

- First, check for monotonicity; if you cannot confirm monotonicity, use the mean value method.
- Then, to get a more accurate enclosure, divide the original interval into two halves, repeat the same procedure for both halves, and take the union of the resulting enclosures.

5. A sample solution to Problem 5

6. (Due September 23) Use the mean value form (with checking
monotonicity first) to estimate the range of the expression
(x_{1})^{2} − x_{1}
* x_{2} + (x_{2})^{2} when x_{1} is
in the interval [0.2, 1], and x_{2} is in the interval [0,
0.6].

7. (Due September 25) Write a method that computes an enclosure for the range of a given function on a given box by using the Mean Value Form. Assume that a function is already implemented as a method f(x) with an array input, and that we have also already implemented a method that computes the enclosures for partial derivatives. For example, in Java, that would mean that we have a method

public static Interval partial(Interval[] inputs, int i){}that, given a box (described as an array of intervals) and an index i, estimates the range of the partial derivative of f over x

8. (Due September 30) Use optimal-side bisection to compute the enclosure for
the expression 2(x_{1})^{2} − 3x_{1}
* x_{2} + 3(x_{2})^{2} when x_{1} is
in the interval [0.2, 1], and x_{2} is in the interval [0,
0.6].

8. A sample solution to Problem 8

9. (Due October 2) Add several iterations of optimal-side bisection to the program that you developed for Problem 7. Test your method on the example of a function and intervals that we had in Problem 6.

10. (Due October 7) Prepare a topic for your class project:

- an ideal project is something related to uncertainty in a research project on which you are working already;
- alternatively, if there is any aspect of computing that excites you, google that topic (e.g., robotics) + interval computations, choose a paper you feel will be of interest to you, and show to the instructor; you will then need to prepare a report (oral and written) on this paper;
- third option is joining one of the projects mentioned in class (see class notes).

11. (Due October 7) Use the interval-based optimization algorithm that
we learned in class to locate the maximum of the function
f(x) = x - x^{2} on the interval [0, 0.8]. Divide this
interval into two, then divide the remaining intervals into two
again, etc. At each iteration, dismiss subintervals where maximum cannot be attained.
Stop when you get intervals of width 0.1.

11. A sample solution to Problem 11

12. (Due October 9) Use the constraints method to solve the following two problems:

- find x
_{1}and x_{2}, both from the interval [0, 2], for which x_{1}− x_{2}= 0 and x_{1}* x_{2}= 1; - find x
_{1}and x_{2}, both from the interval [0, 2], for which x_{1}− x_{2}= 0 and x_{1}* x_{2}= 10.

13. (Due October 21) Submit a written report on what you did for the class project.

14. (Due October 23) Use both linearization algorithms that we
studied in class (Algorithm 1 that uses partial derivatives and
Algorithm 2 which does not) to estimate the range of the function
f(x) = x − 2x^{2} on the interval [0, 0.2]. (The
linearization-based Algorithm 2 is also described in the handout).
Compare the two estimates with the exact range (which you can
compute by using calculus).

15. (Due October 28) Write a program that uses linearization-based Algorithm 2 to estimate the range of a given function on a given box.

16. (Due October 30) Write a program that uses the Monte-Carlo Cauchy algorithm (as described in the handout) to estimate the range of a given function on a given box.

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

18. (Due November 4) For a membership function μ(x) = 1 − |x|, what are the α-cuts corresponding to α = 0.5? to α = 0.2?

19. (Due November 4) 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.

20. (Due November 6) Follow the first two steps of bisection to
locate the square root of 3, i.e., the solution to the equation
x^{2} − 3 = 0 on the interval [0, 2].

21. (Due November 6) Use the explanations that we had in class to
write down a Java method which computes c_{i} =
(f(x_{1}, ..., x_{i−1}, x_{i} + h,
x_{i+1}, ..., x_{n}) − f(x_{1}, ...,
x_{i−1}, x_{i} − h, x_{i+1},
..., x_{n}))/(2h).

22. (Due November 11) Suppose that we have three alternatives, for which the gains are in the intervals [10, 12], [5, 7], and [9, 15].

- 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.

23. (Due November 13) 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.

24. (Due November 13) If we use 2-digit decimal numbers, what will be the result of multiplying the intervals [0.60, 0.75] and [0.12, 1.50]?