For this pseudocode present a loop invariant and prove it, n >= 0. i <= 0;...
For this pseudocode present a loop invariant and prove it, n >= 0.
i <= 0;
s <=2;
while i < n do
i <= i + 1
s <= s * s
Homework Answers
The best loop invariant for this while loop is n-i > 0. Because the loop executes when the value of i is less than n. It terminates once when the i value becomes equal to n.
For example, if n = 5. i = 0 starts with 0.
Iteration 1 : n > i , i = 0, 5 - 0 > 0
Iteration 2 : n > i , i = 1, 5 - 1 > 0
Iteration 3 : n > i , i = 2, 5 - 2 > 0
Iteration 4 : n > i , i = 3, 5 - 3 > 0
Iteration 5 : n > i , i = 4, 5 - 4 > 0
Iteration 6 : n > i , i = 5, 5 - 5 = 0 --> Loop terminates.
From iteration 1 to 5 the loop invariant n - i > 0 holds.
**Comment for any further queries.
Add Answer to:
For this pseudocode present a loop invariant and prove it, n
>= 0.
i <= 0;...
(a) Prove the following loop invariant by induction on the number of loop iterations: Loop Invariant:...
(a) Prove the following loop invariant by induction on the
number of loop iterations: Loop Invariant: After the kth iteration
of the for loop, total = a1 + a2 + · · · + ak and L contains
all elements from a1 , a2 , . . . ,
ak that are greater than the sum of all previous terms of the
sequence.
(b) Use the loop invariant to prove that the algorithm is
correct, i.e., that it returns a...
To prove the correctness of the following: # pre: int >= 1 fac = 1 i...
To prove the correctness of the following:
# pre: int >= 1
fac = 1
i = n
while i>0:
fac = fac*i
i = i-1
# post: fac = n!
which loop invariant do we need?
(Hint, you will need two statements that are both
true. One about fac and one about i)
Please provide both full statements as well as which
loop invariant is needed in a full proof.
2. To prove correctness of the following:...
Use a loop invariant to prove that the following algorithm correctly identifies the location of the...
Use a loop invariant to prove that the following algorithm correctly identifies the location of the minimum value in the array data. Input: data: array of integers Input: n: size of data Output: index min such that data[min] <= data[i] for any i from 1 to n Algorithm: FindMin min = 1; for i = 2 to n do if data[i] < data[min] then min = i; end end return min
Prove procedure to compute Fibinocci(n) where F0 = 0, F1 = 1, Fn = Fn-2 +...
Prove procedure to compute Fibinocci(n) where F0 = 0, F1 = 1, Fn = Fn-2 + Fn-1. Prove by establishing and proving loop invariant then using induction to prove soundness and termination. 1: Procedure Fib(n) 2: i←0,j←1,k←1,m←n 3: while m ≥ 3 do 4: m←m−3 5: i←j+k 6: j←i+k 7: k←i+j 8: if m = 0 then 9: return i 10: else if m = 1 then 11: return j 12: else 13. return k
What is the loop INVARIANT for this program? The loop variant has to pass the premises:
What is the loop INVARIANT for this program? The loop variant
has to pass the premises:
loop {P) [U] while (b) (Sj1 S fQ) (0 S len)) i=0; r false; while (i < len) { if (a ] r) { r = true; i = len; else r true)
loop {P) [U] while (b) (Sj1 S fQ)
(0 S len)) i=0; r false; while (i
Pseudocode (to implement Algorithm); Loop Invariant 4. (15 pts) There is an algorithm called array doubling...
Pseudocode (to implement Algorithm); Loop Invariant
4. (15 pts) There is an algorithm called array doubling that is used to increase the size of an array to accommodate new data when an array fills up. In the algorithm, when an array fills up, a new array is created dynamically that is 2x the size of the original, the data is copied to the new array, and the old array is destroyed (a) Write an algorithm to implement an underflow strategy...
For the while loop below, use the loop invariant given to show that if the pre-condition...
For the while loop below, use the loop invariant given to show that if the pre-condition is the loop.In each step, clearly state true before the loop then the post-condition is true after what facts are assumed and what facts will be proven. (computes the sum of a list of numbers.) fa ,an While (<n) sum := sum + am j j+1 End-while ° Pre-condition: j- 1, sum a, n is a positive integer, a,,.. a, is a list of...
Problem Description proving program correctness Consider the following program specification: Input: An integer n > 0...
Problem Description proving program correctness Consider the following program specification: Input: An integer n > 0 and an array A[0..(n - 1)] of n integers. Output: The smallest index s such that A[s] is the largest value in A[0..(n - 1)]. For example, if n = 9 and A = [ 4, 8, 1, 3, 8, 5, 4, 7, 2 ] (so A[0] = 4, A[1] = 8, etc.), then the program would return 1, since the largest value in...
Loop Invariants. I need help on the 15 point question. The 10 point question is the...
Loop Invariants.
I need help on the 15 point question. The 10 point question is
the "procedure" from the previous question.
2: (10 points) Consider the algorithm for insertion sort shown below. The input to this algorithm is an array A. You must assume that indexing begins at 1. 1: for j = 2: A.length do key = A[j] i=j-1 while i > 0) and A[i] > key do A[i+1] = A[i] i=i-1 A[i+1] = key 3: 4: 5: 6:...
"for every i in 0 to n-1:" This is pseudocode I want to write this in...
"for every i in 0 to n-1:" This is pseudocode I want to write this in python does this mean: "for i in range(0,n-1):"
(a) Prove the following loop invariant by induction on the
number of loop iterations: Loop Invariant: After the kth iteration
of the for loop, total = a1 + a2 + · · · + ak and L contains
all elements from a1 , a2 , . . . ,
ak that are greater than the sum of all previous terms of the
sequence.
(b) Use the loop invariant to prove that the algorithm is
correct, i.e., that it returns a...
To prove the correctness of the following:
# pre: int >= 1
fac = 1
i = n
while i>0:
fac = fac*i
i = i-1
# post: fac = n!
which loop invariant do we need?
(Hint, you will need two statements that are both
true. One about fac and one about i)
Please provide both full statements as well as which
loop invariant is needed in a full proof.
2. To prove correctness of the following:...
What is the loop INVARIANT for this program? The loop variant
has to pass the premises:
loop {P) [U] while (b) (Sj1 S fQ) (0 S len)) i=0; r false; while (i < len) { if (a ] r) { r = true; i = len; else r true)
loop {P) [U] while (b) (Sj1 S fQ)
(0 S len)) i=0; r false; while (i
Pseudocode (to implement Algorithm); Loop Invariant
4. (15 pts) There is an algorithm called array doubling that is used to increase the size of an array to accommodate new data when an array fills up. In the algorithm, when an array fills up, a new array is created dynamically that is 2x the size of the original, the data is copied to the new array, and the old array is destroyed (a) Write an algorithm to implement an underflow strategy...
For the while loop below, use the loop invariant given to show that if the pre-condition is the loop.In each step, clearly state true before the loop then the post-condition is true after what facts are assumed and what facts will be proven. (computes the sum of a list of numbers.) fa ,an While (<n) sum := sum + am j j+1 End-while ° Pre-condition: j- 1, sum a, n is a positive integer, a,,.. a, is a list of...
Loop Invariants.
I need help on the 15 point question. The 10 point question is
the "procedure" from the previous question.
2: (10 points) Consider the algorithm for insertion sort shown below. The input to this algorithm is an array A. You must assume that indexing begins at 1. 1: for j = 2: A.length do key = A[j] i=j-1 while i > 0) and A[i] > key do A[i+1] = A[i] i=i-1 A[i+1] = key 3: 4: 5: 6:...
Most questions answered within 3 hours.
-
lease solve all the
questions, don't need to explanations
Q1 - All animal
species have general...
asked 2 hours ago -
Business Phasing
1.Discuss the logical progression for growing a business, which
starts from the initial idea...
asked 2 hours ago -
Modify
When executing on the command line having only
this program name, the program will accept...
asked 3 hours ago -
Kenny Electric Company's noncallable bonds were issued several
years ago and now have 20 years to...
asked 4 hours ago -
find H(e^Jtheta) at theta= 0, pi/10, pi/20, pi/2 for
the following:
a) H(e^Jtheta)= 1+e^Jtheta
b) H(e^Jtheta)=...
asked 4 hours ago -
Home Corporation will open a new store on January 1. Based on
experience from its other...
asked 4 hours ago -
In a neoclassical model, use the IS-LM to analyze the effect of
a permanent money supply...
asked 5 hours ago -
An electron passes through a point 2.67 cm from a long straight
wire as it moves...
asked 6 hours ago -
A grammar is a 4-tuple G, G = (Ν, Σ, Π, Σ, S) where, Ν is...
asked 6 hours ago -
In this part, calculate the present values. Use the Excel PV
function to compute the present...
asked 6 hours ago -
Part 1. Primitive Types, Sorting, Recursion for
Homework.java
a) Implement the static method initializeArray that receives...
asked 7 hours ago -
Using C++, build a sorter that can rank a sequence of numbers in
a descending order....
asked 7 hours ago