Write a pseudocode function R2(key, A, B, N) that takes a non-negative integer key, andarraysAandB,aswellasthelengthofA,N: thefunctionshouldreturn-2ifthevalues in B do not correspond to the sums of values in A; if no error has been found the function should return the index if key is found in A, or -1 if key has not been found. 2.The Theta notation derive the worst-case running time T(N) of the algorithm R2. Describe the steps taken in your reasoning about what is the worst-case input and the resulting worst-case running time. 3.Very briefly explain why not all errors that can occur for array A will be detected in the method above
function Sum(A,left,right)
if left > right:
return 0
else if left = right:
return A[left]
mid = floor(N/2)
lsum = Sum(A,left,mid)
rsum = Sum(A,mid+1,right)
return lsum + rsum
function CreateB(A,N)
B = new Array of length 1
B[0] = Sum(A,0,N-1)
return B
Building on the above, in a new scenario, given an array A of non-negative integers of length N, additionally a second array B is created; each element B[j] stores the value A[2*j]+A[2*j+1]. This works straightforwardly if N is even. If N is odd then the final element of B just stores A[N-1] as we can see in the figure below: (added in image)
The second array B is now introducing redundancy, which allows us to detect if there has been a hardware failure: in our setup, such a failure will mean the values in the arrays are altered unintentionally. The hope is that if there is an error in A which changes the integer values then the sums in B are no longer correct and the algorithm says there has been an error; if there were an error in B the values would hopefully be incorrect
From now on in this assignment we will assume that at most one array might have its values altered, but we do not know which one ahead of time.
The goal is now to write an algorithm to search for a non-negative integer in the array A, but also to check for errors in the arrays. If there has been an error determined from checking both A and B, and an appropriate error value should be returned. If no errors are detected then we determine if the integer is in A or not.
Task 3: Complete the following:
1. Write a pseudocode function R2(key, A, B, N) that takes a non-negative integer key, andarraysAandB,aswellasthelengthofA,N: thefunctionshouldreturn-2ifthevalues in B do not correspond to the sums of values in A; if no error has been found the function should return the index if key is found in A, or -1 if key has not been found.
2.The Theta notation derive the worst-case running time T(N) of the algorithm R2. Describe the steps taken in your reasoning about what is the worst-case input and the resulting worst-case running time.
3.Very briefly explain why not all errors that can occur for array A will be detected in the method above.
Step by step
Solved in 4 steps with 1 images
