## CS 2401 Assignment #4

Due Date: Thursday, July 5.

Objective: The goal of this assignment is to practice recursion.

Background. In 2008, three UTEP students participated in the Olympic Games. Let us help a UTEP athlete train for the future Olympics. Specifically, he trains for a 100 meter race. The world record is w = 9.58 sec. After each training session, the difference r − w between the athlete's running time r and the world record w decreases by a constant factor f (depending on the athlete). To be more precise, the running times r(t+1) and r(t) after two consequent training sessions are related by the formula r(t + 1) − w = f * (r(t) − w), which is equivalent to

r(t + 1) = w + f * (r(t) − w).
From this equation, we can determine the parameter f if we know the running times r(0) and r(1) before and after the first training session, as
f = (r(1) − w) / (r(0) − w).
Once the value f is determined, we now need to compute, for a given integer T, the expected running time r(T) after the T-th training session.

Assignment. Write two methods that, given:

• the running time r(0) before the first training session,
• the running time r(1) after the first training session, and
• the total number T of training sessions,
predict the athlete's running time r(T) after all T training sessions:
• a method based on recursion and
• an iterative method that uses a simple for loop.
In both methods, we should first compute the factor f as
f = (r(1) − w) / (r(0) − w),
and then the values r(t) by using the relation
r(t + 1) = w + f * (r(t) − w).
(The ideas behind both methods are explained in similar examples in the class and in the book.)

Once the methods are up and running, compare the speed of these two approaches by using the same techniques as in Assignment 3. Record your observations and be able to explain what is happening to your TA when you demo your program.

Testing. Do not forget to test your method. To test your method, pick any value of r(1) and f. For example, if you take r(0) = 10.0 and f = 0.5, then you should get

r(0) − w = 10.0 − 9.58 = 0.42,
so
r(1) = w + 0.5 * (r(0) − w) = 9.58 + 0.5 * 0.42 = 9.58 + 0.21 = 9.79,
and similarly,
r(2) = w + 0.5 * (r(1) − w) = 9.58 + 0.5 * 0.21 = 9.58 + 0.105 = 9.685,
and
r(3) = w + 0.5 * (r(2) − w) = 9.58 + 0.5 * 0.105 = 9.58 + 0.0525 = 9.6325,
etc. This means that your program, when you pass it the values r(0) = 10.0, r(1) = 9.79, and T = 3, should return 9.6325 as the value for r(T). Specifically, your program should first find the factor f by applying the above formula, then compute r(2) and r(3). Feel free to test your method on other similar examples as well: the more you test, the more confident you will be that your program is correct.