JAVA

2. Participation

Consider the following small program:

int SumBetween (int X, int Y)

// pre : X <= Y

// post : returns the sum X + (X+1) + ... + Y

{

int sum = 0;

for (int i=X; i!=Y+1; i++)

sum += i;

}

(a) State the loop invariant. (Hint: Use the example for summing the numbers between 0 and N discussed in lectures.)

(b) Show that the loop invariant is established by the initialization.

(c) Verify that the loop invariant is preserved by each iteration of the loop.

(d) Show that the loop invariant and the termination condition imply the post-condition.

(e) Assuming that addition is the most expensive operation, what is the complexity in big oh notation of this program?

3. Participation

One of the tricks to designing algorithms is to reuse strategies from similar problems. The following question concerns an application of binary search to a different problem. The reason we can use binary search is because the problem can be thought of as searching an ordered array of integers, even though we dont actually implement the array. The integer square root of an integer n is defined to be the integer m such that m^2 n < (m + 1)^2 . Use a binary search strategy to write a function to find the integer square root.