Let n be a positive integer. We are given as input two integers, each with n dig
ID: 3690627 • Letter: L
Question
Let n be a positive integer. We are given as input two integers, each with n digits, and we want to determine which of the integers is larger by only comparing individual digits. For example, if the input were 1234; 2468, the output would be 2468. Also, if the input were 123; 123, the output would be 123. Suppose we have access to a subroutine called Smaller Digit(x_1 ; x_2), which takes as input two individual digits (0 through 9) x_1 and x_2 and returns true if and only if X_1 is smaller than x_2. For example, Smaller Digit (0 ; 4) would return true, while Smaller Digit (6 ; 4) would return false. Also, Smaller Digit(4 ; 4) would return false. Assume that, the subroutine Smaller Digit takes constant time oil any input of two individual digits. Here is an iterative algorithm to solve this problem. Larger Integer(a_1 a_2...a_n ; b_1 b_2...b_n : two integers with n digits each) for i := 1 to n if Smaller Digit(a_i, b_i) then return b_1 b_2...b_n if Smaller Digit(b_i, a_i) then return a_1 a_2...a_n return a_1 a_2...a_n Prove the following loop invariant for this algorithm: After k iterations of the for loop, if the algorithm has not yet terminated, we know a_1 a_2...a_k = b_1 b_2...b_k.Explanation / Answer
To show correctness, we shall use the following loop invariant:
• Initialization: At the beginning of the first iteration, we have
i = 1 to n, so the statement is empty.
• Maintenance: Suppose the invariant is not maintained after
the k-th iteration. We would then have some i k 1 such
that smaller digits of the two is returned. We shall be doing this for each
of the n values in the number. The Smaller function shall keep returning the smallest of the two ,
and we will be returning the larger number in the end.
• Termination: Since the loop is a for loop over a finite sequence
1 ...n, the loop will always terminate. If the algorithm
finds larger number at the kth ppoint (or the kth value of i), so the loop
invariant is true (and the algorithm returns the index i). Otherwise,
the loop terminates after n iterations, in which
case the invariant is again true, and
the algorithm returns the larger number of the two.
Therefore, the function LargerInteger is correct by the loop invariant.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.