Recall the randomized version of linear search we talked about in class: Linear-
ID: 3869562 • Letter: R
Question
Recall the randomized version of linear search we talked about in class:
Linear-Search(A,k)
while A not empty
x = random number between 1 and A.length
if A[x] = k
return x
remove A[x] from A
return -1
This is an example of a Las Vegas algorithm, because it guarantees correctness -- it will return the position in A of the target k, or -1 if k does not exist in A -- but it might be just as slow as the original linear search.
For this problem, rewrite the algorithm above to turn it into a Monte Carlo algorithm -- one that is guaranteed to take fewer than A.length steps, but that might not find k in A. Follow the pseudocode conventions of this course.
Explanation / Answer
The basic difference between Monte Carlo and Las Vegas is that in Monte Carlo we guess that we have the right answer and maybe our output may be incorrect. However, in Las Vegas we know that the answer is in somewhere but complesxity is the issue here. The given can be converted into Monte Carlo in many ways, one such possible way can be using random addition to the index.
Linear-Random-Search(A,k)
jump = random number from 2 to A.length
i=0
while i less than A.length
if A[i] = k
return i
i+=jump
return -1
In the above case we have generated a random value to jump and see if our values lies there. I hope you understood it, for further query do comment.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.