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:

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

4. (Due September 21) We want to estimate 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].

- find the exact range by using calculus;
- estimate the range by applying naive (straightforward) interval computations to the original intervals;
- use bisection and apply naive interval computations to both sub-boxes.

5. (Due September 23) To estimate 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], we bisected the original box
into four sub-boxes, with x_{1} in [-1, 0] and [0, 1], and
x_{2} 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 x_{1} is in [0, 1], and
x_{2} 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
(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].

9. (Due October 14) Use the
mean value form 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].

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 + x^{2} 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) = x^{2} - 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)

- Implement four basic operations of interval arithmetic.
- 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_{i}. Test your method on the example of a function and intervals that we had in Problem 9.

12. (Due October 26) Use the interval-based optimization algorithm that
we learned in class to locate the maximum of the function
f(x) = 2x_{1}^{2} - 2x_{1} * x_{2} +
x_{2}^{2} + x_{1}
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:

- find x
_{1}and x_{2}, both from the interval [-10, 10], that satisfy the system of equations x_{1}+ x_{2}= 0 and x_{1}* (1 + x_{2}) = 0.21; - find x
_{1}and x_{2}, both from the interval [-10, 10], that satisfy the system of equations x_{1}+ x_{2}= 0 and x_{1}* (1 + x_{2}) = 0.3.

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

- for
the first alternative a
_{1}, the range of possible benefits is [1.0, 2.0]; - for
the second alternative a
_{2}, the range of possible benefits is [0.0, 3.0]; - for
the third alternative a
_{3}, the range of possible benefits is [-1.0, 3.0].

- a pessimist, for whom α = 0;
- an optimist, for whom α = 1;
- a decision maker for whom α = 0.5;
- a decision maker for whom α = 0.3.

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

- a number a
_{0}(describing the results of computations with midpoints); - an array a
_{1}, ..., a_{n}(describing the coefficients at Δa_{i}), and - an interval [a] (describing the effect of quadratic and higher order terms).

- a
_{0}= X_{i}; - a
_{i}= -1 and a_{j}= 0 for all j =/= i; and - [a] = [0, 0].

- a method that transforms each input interval into the corresponding generalized interval;
- a method for adding generalized intervals, i.e., a method that takes as inputs generalized inputs corresponding to two quantities a and b, and produces a generalized interval corresponding to c = a + b;
- a method for subtracting generalized intervals, i.e., a method that takes as inputs generalized inputs corresponding to two quantities a and b, and produces a generalized interval corresponding to c = a - b;
- a method for multiplying generalized intervals, i.e., a method that takes as inputs generalized inputs corresponding to two quantities a and b, and produces a generalized interval corresponding to c = a * b;
- a method that transforms the generalized interval
(a
_{0}, (a_{1}, ..., a_{n}), [a]) corresponding to the final result into the final interval estimatea _{0}+ a_{1}* [-Δ_{1}, Δ_{1}] + ... + a_{n}* [-Δ_{n}, Δ_{n}] + [a].