CS 5351/CS 4365, Fall 2010, Final Exam

Name: ___________________________________________________________

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

2-3. Given the following number of people in each age bracket: [0, 20]: 1, [20, 30]: 2, [30, 50]: 1, compute the range of possible values of the variance.

4. Give two numerical examples when an optimizing compiler helps improve the interval estimate, and a numerical example when an optimizing compiler makes the excess width worse.

5-6. Use calculus to find 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 [-3, 3]. Use naive interval computations to estimate this range.

7. Assuming that the computer uses 2 decimal digits, compute the range of a - b * c, where a is in the interval
[0.8, 1.2], b is in the interval [0.7, 1.1], and c is in the interval [2.2, 3.3], with appropriate round-offs.

8-10. Estimate the range of function (1 + x) * (2 - x) on the interval [1.0, 3.0] by using the following methods:

• use the centered form;
• use the mean valued form;
• use affine arithmetic.

11. A decision maker has three alternatives:

• for the first alternative a1, the range of possible benefits is [100.0, 200.0];
• for the second alternative a2, the range of possible benefits is [0.0, 300.0];
• for the third alternative a3, the range of possible benefits is [-50.0, 300.0].
Find out which alternative will be selected by each of the following four decision makers:
• a pessimist, for whom α = 0;
• an optimist, for whom α = 1;
• a decision maker for whom α = 0.5.

12. Use the interval-based optimization algorithm to locate the maximum of the function f(x) = x - x2 on the interval [0.2, 1.0]. Divide this interval into two, then divide the remaining intervals into two again, etc. Stop when you can locate the maximum with accuracy 0.1.

13-14. Use the constraints method to solve the following two problems:

• find x1 and x2, both from the interval [-10, 10], that satisfy the system of equations x1 - x2 = 0 and
x1 * (1 - x2) = 0.16;
• find x1 and x2, both from the interval [-10, 10], that satisfy the system of equations x1 - x2 = 0 and
x1 * (1 - x2) = 1000.

15. Describe, in as many details as you can, one of class project presentations (different from your own).