CSCI5454 Homework 1- Analysis of Algorithms, Euclid’s Algorithms and its analysis Solution

P1. Consider the extended Euclid’s algorithm that was taught in class.
1 def extended gcd (a0 , b0 ):
2 #precond : a0 ≥ 1,b0 ≥ 0,a0 ≥ b0
3 (a , b) = (a0 , b0) # I n i t i a l i z e
4 (s , t ) = (1 , 0) # I n i t i a l i z e Bezout co ef fic ien ts for a
5 (sˆ, tˆ) = (0 , 1) # I n i t i a l i z e Bezout co ef fic ien ts for b
6 while ( b > 0 ):
7 (q , r ) = (a//b, a % b) # compute quotient and reminder
8 (a , b) = (b, r ) # update a , b
9 # update the Bezout c oef fi cie nts
10 (s , t , ˆs , tˆ) = (sˆ, tˆ, s − q ∗ sˆ, t − q ∗ tˆ)
11 return (a , s , t )
Part A (10 points) Prove the loop invariants:
a = sa0 + tb0, and b = saˆ 0 + tbˆ 0
Your proof should clearly split into base case and inductive step. Expected solution should follow same format as an example we will post for the class. Unclear proofs will not get any credit.
Part B (5 points) Prove B´ezout’s Lemma: for all integers a > 0 and b ≥ 0, gcd(a,b) is the smallest positive number that can be written as sa + tb for some integers s,t.
Hint: Break it into two parts. First show that the GCD can be written as sa + tb for some integers s,t. Use the work you did from the previous problem. Next, prove that the GCD divides any positive number of the form la+ub. Proof will require 5 lines. Please be precise in your arguments.
(Etienne B´ezout :´ https://mathshistory.st-andrews.ac.uk/Biographies/Bezout/).
Part C (5 points) Let n < p be natural numbers that are relatively prime (i.e, they have no prime factors in common). Prove that there exists a unique number m (modulo p) such that n × m = 1 mod p. Proof takes < 10 lines and uses B´ezout theorem above. (Note: m is called the modular inverse of n modulo p. We need to perform modular inverse computation as part of RSA public/private key generation).
Part D (5 points) How would you compute the modular inverse of a number n modulo p if n,p are relatively prime? Compute the modular inverse of n = 13113 modulo p = 2133555512. Hint: use the B´ezout coefficients s,t from the extended Euclidean algorithm above.
This list ℓ of length n represents that Jane earned $ 5 in her trade number 0, earned $ 10 in trade number 1, lost $4 in trade number 2 and so on.
1
Thus given a list of returns from trades, we wish to support queries where each query inputs two indices (i,j) where 0 ≤ i ≤ j < n and needs to output the sum ℓ[i] + ··· + ℓ[j].
Part A (5 points): If you are allowed to store O(n) extra space for Jane, describe how would you use it to support each query in O(1) time? Describe the pre-processing algorithm and the algorithm for handling queries separately. How many steps does your pre-processing need? (expected: 5 lines).
√
Part B (5 points) Suppose the extra space allowed is reduced to O( n) instead of O(n), describe how you would pre-process and support queries with this new space restriction? How many steps does your pre-processing take? How much time would each query require? (expected : 5 lines).
Part C ( 10 points) Let us take a small diversion to solve the following problem.
Given a non-empty sorted array of numbers A of length n and a number x, find the index j such that A[j] is the largest number in A such that A[j] ≤ x. Assume that the inputs satisfy A[0] ≤ x. We will assume python convention that arrays are indexed from 0 to n − 1, inclusive.
Example: Suppose A : [1,5,10,12,15,18] and x = 14, we will return 3 with A[3] = 12 as the largest element ≤ 14.
We would like you to modify binary search to find such an index j in time Θ(log(n)) worst case. Here is the template for the pseudo-code and the loop invariant we would like to establish. Fill in the rest of the outline below so that you are guaranteed a terminating and correct algorithm.
1 def findLargestIndex (A, x ):
2 assert ( A[0] <= x)
3 n = len(A)
4 if (x >= A[n−1]):
5 return n−1
6 # TODO: I n i t i a l i z e two indices l , u
7 l = . . .
8 u = . . . .
9 # Loop Invariants : 0 <= l < u < n and A[ l ] <= x < A[u ]
10 while ( . . . ): # f i l l in the appropriate termination condition 11 mid = ( l + u) /2 # This w i l l be integer division 12 # Compare A[ x ] to A[ mid ] and update l , u.
13 # Be careful to make sure that the loop invariants are maintained .
14 . . .
15 return . . . # what should we return?
Complete the algorithm above and give a brief explanation (≤ 5 lines) of why it works. It will help if you ran it and tested it as well. For the solution, just complete the pseudocode and explain why the loop invariants hold.
Part D (5 points) Returning back to the list of trades ℓ of Jane, describe an algorithm that given two indices 0 ≤ i ≤ j < n will tell us if Jane had any trade k between times i and j that resulted in a loss. In other words, does there exist index i ≤ k ≤ j such that ℓ[k] < 0? Your algorithm should return yes/no and for a yes answer it should also return the index k above.
You are allowed O(n) extra space and O(n) time to pre-process the data. Each query should be supported in O(1) time.
2