Question

In: Computer Science

Python Loop invariant To show that an assertion A is a loop invariant , is it...

Python Loop invariant

To show that an assertion A is a loop invariant , is it enough to argue that the execuation of the loopbody preserves A? Please desscribe it throughly.

Solutions

Expert Solution

On each loop we write, we should always ask this crucial question:

Say that several iterations of the loop have been running; what has it achieved so far?

The response to the factorial illustration is:

Factor fact has the meaning following i iterations, fac = = i!.

This response is significant because it demonstrates the method used by the loop to achieve its target in stages: as i count upwards towards n, fac = = i That holds true repeatedly. And when i = = n, the loop ends, this means that the loop can accomplish its goal: fac = = n!.

The answer to the "key question" mentioned above is the invariant property of the loop.

This is because the output from the previous iterations of the loop flows into the next iteration of the loop. So, iteration after iteration after iteration, whatever is done looks the same. This is a logical property which can be demonstrated.

The argument that results from performing one more iteration of the loop is the same as the statement we had when we began the iteration.


Related Solutions

According to the loop invariant theorem, a valid loop invariant ?(?)I(n) must have the property that...
According to the loop invariant theorem, a valid loop invariant ?(?)I(n) must have the property that Select one: a. ?(?)=0I(n)=0 after a finite number of steps. b. After the loop, ?→?(?)P→I(N) where ?P is the postcondition. c. ?(0)→?I(0)→Q, where ?Q is the precondition. d. None of the other answers are correct
Find a loop invariant (I) for the following while loop with the post-condition {Q: S=1}, where...
Find a loop invariant (I) for the following while loop with the post-condition {Q: S=1}, where S is an integer and the operator / represents an integer division. Show your work step by step to receive full credit. while (S > 1) do S = S / 2; }
Write the loop invariant for the following program the computes quotients (q) and remainders (r) of...
Write the loop invariant for the following program the computes quotients (q) and remainders (r) of “a” divided by ”d”. Then prove all three cases (Initialization, Maintenance, Termination). Assume “a” and “d” are positive integers. r=a q=0 while r>=d             r=r-d             q=q+1
in python please ,, A SOON AS POSSIBLE PLEASE #Class invariant for SimpleQueue, a queue based...
in python please ,, A SOON AS POSSIBLE PLEASE #Class invariant for SimpleQueue, a queue based on a linked list # 1. The queue is a linked list of ListNode objects. # 2. A SimpleQueue object has instance variables self.head, a reference to the node at the front of the queue, self.tail, a reference # to the node at the end of the queue, and self.size, the number of nodes in the queue. # 3. If self.size = 0, then...
python Write a Loop class. The contents of a loop object are represented internally as a...
python Write a Loop class. The contents of a loop object are represented internally as a simple python list with the following additional instance variables: loop - a python list containing the elements of the loop list head - which stores the index of the first element of the loop list current - which stores the index of the last element of the loop list size - which stores how many actual elements are in the loop max - which...
Show that two m×n matrices are equivalent if and only if they have the same invariant...
Show that two m×n matrices are equivalent if and only if they have the same invariant factors, i.e. (by Problem 4), if and only if they have the same Smith normal form.
Write a python code which prints triangle of stars using a loop ( for loop )...
Write a python code which prints triangle of stars using a loop ( for loop ) Remember what 5 * "*" does The number of lines of output should be determined by the user. For example, if the user enters 3, your output should be: * ** *** If the user enters 6, the output should be: * ** *** **** ***** ****** You do NOT need to check for valid input in this program. You may assume the user...
Create Python Code using a "for" loop and a "while" loop. You are starting a twelve...
Create Python Code using a "for" loop and a "while" loop. You are starting a twelve week program training to compete in a triathlon. The triathlon consists of three athletic events, 1.5 k swim, 40k bike, 10k run. In order to be prepared for the competition you want to print a training schedule. Starting with week 1 you will increase the distance of each activity so that you reach the race distance by week twelve. Due to rounding, you may...
Can you please explain loop invariant for Heapsort, in which Min-Heapify and Build-Min-Heap are correct
Can you please explain loop invariant for Heapsort, in which Min-Heapify and Build-Min-Heap are correct
Hello, as we know the invariant for the insertion sort is Invariant: at the start of...
Hello, as we know the invariant for the insertion sort is Invariant: at the start of each for loop, A[1…j-1] consists of elements originally in A[1…j-1] but in sorted order Please proof this invariant by mathematical induction method.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT