Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
The algorithm of Euclid computes the greatest common divisor (GCD) of two integer numbers a and b. The following pseudo-code is the original version of this algorithm.  Algorithm 1 Euclid1(a,b) Require: a, b > 0 Ensure: a = GCD(a, b)     while a ̸= b do         if a > b then             a ← a − b         else             b ← b − a         end if     end while return a We want to prove the correctness of this algorithm using the loop invariant technique. Answer the following questions: a. Show the property is maintained during the execuation of the While loop (i.e., maintenance property). b. Prove the termination property and conclude. c. What would happen if a > 0 and b = 0 and thus the pre-condition is not satisfied?

The algorithm of Euclid computes the greatest common divisor (GCD) of two integer numbers a and b. The following pseudo-code is the original version of this algorithm.  Algorithm 1 Euclid1(a,b) Require: a, b > 0 Ensure: a = GCD(a, b)     while a ̸= b do         if a > b then             a ← a − b         else             b ← b − a         end if     end while return a We want to prove the correctness of this algorithm using the loop invariant technique. Answer the following questions: a. Show the property is maintained during the execuation of the While loop (i.e., maintenance property). b. Prove the termination property and conclude. c. What would happen if a > 0 and b = 0 and thus the pre-condition is not satisfied?

icon
Related questions
Question

The algorithm of Euclid computes the greatest common divisor (GCD) of two integer numbers a and b. The following pseudo-code is the original version of this algorithm. 

Algorithm 1 Euclid1(a,b)
Require: a, b > 0
Ensure: a = GCD(a, b)
    while a ̸= b do
        if a > b then
            a ← a − b
        else
            b ← b − a
        end if
    end while
return a

We want to prove the correctness of this algorithm using the loop invariant technique. Answer the following questions:

a. Show the property is maintained during the execuation of the While loop (i.e., maintenance property).

b. Prove the termination property and conclude.

c. What would happen if a > 0 and b = 0 and thus the pre-condition is not satisfied?

Expert Solution
steps

Step by step

Solved in 4 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Greatest Common Divisor
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, data-structures-and-algorithms and related others by exploring similar questions and additional content below.