Lectures #53 and #55



Yüklə 10,07 Kb.
tarix17.11.2018
ölçüsü10,07 Kb.
#80029

Lectures #53 and #55
1. Assume at the start of the loop that lowEnough = 0, tooHigh = 102, and x = 101. What are the values of lowEnough and tooHigh when the loop exits?
/**

* @updates lowEnough, tooHigh

* @maintains lowEnough <= sqrt(x) AND tooHigh > sqrt(x) AND

* tooHigh > lowEnough

* @decreases tooHigh - lowEnough

*/

while(tooHigh – lowEnough > 1){



}
1a. Are all three parts of the loop invariant necessary here? Could you still make the same argument as before if one of them was missing?


2. Assume at the start of the loop that s = "Lollapalooza", entrySet = {}, and i = 0. What are the values of entrySet and i when the loop exits?

/**


* @updates entrySet, i

* @maintains i <= |s| AND

* entrySet = entries(s[0, i))

* @decreases |s| - i

*/

while(i < s.length()){



}
3. Assume at the start of the loop that left = <16, 9>, right = <1, 4, 9, 16, 4, 1>. What are the values of left and right when the loop exits?


/**

* @updates left, right

* @maintains rev(#left) * #right = rev(left) * right AND

* [right is not empty]

* @decreases |right|

*/

while(right.length() > 1){



}
4. Consider the following code, which is the body of a method to find the minimum value in an array. What could you use as a loop invariant to prove this code is correct? How about a progress metric? Assume that the array has a length of at least 2.


int min = values[0];

int i = 1;

while(i < values.length){

if(values[i] < min){

min = values[i];

}

i++;



}

return min;
Yüklə 10,07 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə