Consider the following program, which takes as input an integer n > 0, and returns some...

 

Transcribed Image Text:

Consider the following program, which takes as input an integer n > 0, and returns some other integer as a result. P(n) { i = 0; 8 := 0; while (i < n) do i=i+1 s = sti return s (a) Compute P(n) on a few test values of your choice, and determine the function g(n) computed by the program. Your answer should include at least 5 tests, but you do not need to include the intermediate steps of the computation. (You may run the program on a computer if you like.) (b) Prove that the program P(n) computes the function g(n) by presenting an appropriate loop invariant for the program. Your solution should include a clear description of the loop invariant, a proof that the loop invariant is correct, and a proof that the correctness of the program follows from the loop invariant. Consider the following program, which takes as input an integer n > 0, and returns some other integer as a result. P(n) { i = 0; 8 := 0; while (i < n) do i=i+1 s = sti return s (a) Compute P(n) on a few test values of your choice, and determine the function g(n) computed by the program. Your answer should include at least 5 tests, but you do not need to include the intermediate steps of the computation. (You may run the program on a computer if you like.) (b) Prove that the program P(n) computes the function g(n) by presenting an appropriate loop invariant for the program. Your solution should include a clear description of the loop invariant, a proof that the loop invariant is correct, and a proof that the correctness of the program follows from the loop invariant.