3. In the following question assume that you are given a function EDist (point1,
ID: 3740526 • Letter: 3
Question
3. In the following question assume that you are given a function EDist (point1, point2) which calculates the distance between point! (p1,P2) and point2 (P3,ps), where Pi, p2,Ps, and p4 are integers. (pointl, and point2 are two points in the Euclidian plane.) Assume that EDist is correct. (a) Give an appropriate loop invariant for the purpose of proving the partial correctness of the algo- (b) Use your loop invariant from part (a) to prove the partial correctness of Algorithm3 with respect (c) Prove your loop invariant. ith respect to its given specification to the given specification Precondition: A is a list of points in the Euclidian space, each given as a pair of integers, and len(A) > 1, and 0Explanation / Answer
a) The Loop invariant for the Algorithm will be:-
for (startPos = End; startPos > 0; startPos = startPos -1){
if (startPos == 1) return (A[0], A[1])
// rest of code goes here
}
b) So, we have an Initial Starting Location at 0, and we need to move to Destination say 10, and to find the minimal distance between 0...10 points, we will decrement from 10 (move backwards from 10) until we reach point 1, after which we cannot move more backwards as we are already starting from Point 0. So, our loop starts with End Position (10) and we put the logical check until we reach the starting position (ie 0) and every time loop is executed we move the loop counter backwards from 10 (to 9, next 8, next 7, and so on....) until we meet at point 1 after which loop will terminate. Thus this way the loop variant will compute the Algorithm3.
(c) Lets us take an example for Start Position = 0, and End Position say 10;
for (startPos = 10; startPos > 0; startPos --){
if (startPos == 1) // meaning we have already moved backwards to the starting point and hence cant move.
return (A[0], A[1]);
else{
// code for compute Edist() goes here
}
// After this point the startPos will be 9, 8, 7, 6, 5.....till it reaches 1, when it will terminate the loop.
}
Please let me know in case of any clarifications required. Thanks!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.