CISC/CMPE 223 - Assignment 8(Winter 2019)

ASSIGNMENT > CISC/CMPE 223 - Assignment 8(Winter 2019)

No School AA 1 One bonus mark for neatly written student information: Papers that have all the names and student numbers written exactly as requested in the regulations (found at the end), will receive one bonus mark. 1. (2 marks) Verify the validity of the following correctness statement by adding all the intermediate assertions. All variables are ...[Show More]

No School
AA 1
One bonus mark for neatly written student information: Papers that have all the names and

student numbers written exactly as requested in the regulations (found at the end), will receive

one bonus mark.

1. (2 marks) Verify the validity of the following correctness statement by adding all the intermediate assertions. All variables are of type int Also state any mathematical facts used.

ASSERT( y == 0 || z > -1 )

x = z-y;

z = x+y;

y = x-z;

ASSERT( x >= y || z == x+y )

2. Assume a declarative context where x, y and z have type integer.

Consider the following (partial) correctness statement. The associated code is supposed

to compute the product of x and y using only addition and subtraction.

ASSERT ( P ) /* weakest pre-condition that guarantees termination */

{ int i;

z = y; i = x-1;

while ( i != 0 ) INVAR( ... what can be used as the invariant ? ... )

{ z = z + y; i = i - 1; }

}

ASSERT ( z == x * y )

(a) (1 mark) Give the weakest sufficient pre-condition P (on the values of x and/or y)

that guarantees the termination of the loop. Briefly explain your answer.

(b) (2 marks) Give a loop invariant for the while-loop that can be used to verify the

correctness and termination of the code assuming that your pre-condition P holds.

Note: In this question you do not need to write the complete proof tableau.

This study source was downloaded by 100000875661904 from CourseHero.com on 03-25-2024 16:09:30 GMT -05:00

https://www.coursehero.com/file/45307201/a8pdf/

3. (5 marks) Select a loop invariant and give a complete proof tableau (that is,

add all the intermediate assertions) for the following correctness statement. Also make

an argument for termination. The value k is constant integer and all variables are of type

integer.

ASSERT(k >= 0)

{ i = 1;

g