Interval Computations,
Homeworks for the course
CS 5351/CS 4365, Fall 2010

1. (Due September 9) Given the following number of people in each age bracket: [0, 60]: 1, [70, 80]: 2, [80, 100]: 1, compute the range of possible values of the variance.

2. (Due September 14) Write a program that, given n intervals (as in the privacy case), computes the range of possible values of the variance.

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

4. (Due September 21) We want to estimate the range of a function f(x1, x2) = (x1)2 - x1 * x2 +(1/2) * (x2)2 + x2 when x1 is in the interval [-1, 1], and x2 is in the interval [-2, 2].

5. (Due September 23) To estimate the range of a function f(x1, x2) = (x1)2 - x1 * x2 +(1/2) * (x2)2 + x2 when x1 is in the interval [-1, 1], and x2 is in the interval [-2, 2], we bisected the original box into four sub-boxes, with x1 in [-1, 0] and [0, 1], and x2 in [-2, 0] and [0, 2]. In class, we used monotonicity analysis to simplify and improve the estimation of the range for one of the 4 sub-boxes, when x1 is in [0, 1], and x2 is in [-2, 0]. Perform a similar analysis for the three remaining sub-boxes. Reminder: when there is no monotonicity, we have no other choice but to use naive interval computations.

6. (Due October 5) Propose a topic for a project that you want to do for this class.

7. (Due October 12) Assuming that the computer uses 2 decimal digits, compute the range of a + b * c, where a is in the interval [-1.1, -0.9], b is in the interval [0.010, 0.013], and c is in the interval [11, 15], with appropriate round-offs.

8. (Due October 12) Use both naive interval computations and centered form to estimate the range of the expression (x1)2 - x1 * x2 + (x2)2 when x1 is in the interval [0.2, 1], and x2 is in the interval [0, 0.6].

9. (Due October 14) Use the mean value form to estimate the range of the expression (x1)2 + x1 * x2 + (x2)2 when x1 is in the interval [0.2, 1], and x2 is in the interval [0, 0.6].

10. (Due October 19) Use the interval-based optimization algorithm that we learned in class to locate the maximum of the function f(x) = x + x2 on the interval [-0.8, 0]. Divide this interval into two, then divide the remaining intervals into two again, etc. Stop when you get intervals of width 0.1.

10a. (Due October 26) Use the interval-based optimization algorithm that we learned in class to locate the maximum of the function f(x) = x2 - x + 1 on the interval [-0.6, 1]. Divide this interval into two, then divide the remaining intervals into two again, etc. Stop when you get intervals of width 0.1.

11. (Due October 21)

12. (Due October 26) Use the interval-based optimization algorithm that we learned in class to locate the maximum of the function f(x) = 2x12 - 2x1 * x2 + x22 + x1 on the box [-1, 1] X [-1, 1]. Two bisection cycles are enough.

13. (Due November 2) Write a method that uses the algorithm that we learned in class to locate the maximum of an arbitrary function on a given box. Just like in the previous programming assignment, 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.

14. (Due October 28) Use the constraints method that we had in class to solve the following two problems:

15. (Due November 4) For the problem that we started in class -- applying constraints techniques to solving a cubic equation x3 - 3x2 + 3x - 9 = 0 for x in [0, 10], perform two loops for x in the first sub-interval [0, 5]. For the auxiliary variables, start with the ranges that we have obtained for them by analyzing the original interval [0, 10].

16. (Due November 9) A decision maker has three alternatives:

Find out which alternative will be selected by each of the following four decision makers:

17. (Due November 11) In the affine arithmetic, instead of intervals, we have generalized intervals. Each generalized interval consists of the following three fields:

In the beginning, each value from the original input interval [Xi - Δi, Xi + Δi] is represented as Xi - Δxi, i.e., as a generalized interval with In addition to generalized intervals corresponding to different intermediate results, we can also store the array of values Δ1, ..., Δn. In Java, they can be stored as static. The task is to implement the following methods: