PLEASE GUIDE ONLY NUMBER #2'S PROCEDURE PLEASE! :) THANK YOU VERY MUCH IN ADVANCE!

You are a police officer trying to crack a case. You want to check whether an important file is in the evidence room. Files have IDs that are positive integers and the evidence room contains n files in sorted order of their IDs. Unfortunately, you do not have direct access to the evidence room; the only one who has access is Randy, who is corrupt and wants to make things hard for you. In the following we assume that r is the file ID you are looking for. I. You know that the evidence room is organized as a sorted list of n elements. If Randy was not corrupt you would probably do binary search by asking him to give you the median file of the list. Unfortunate ly, you can only give Randy two indices, u and he returns to you a file with index chosen uniformly at random from the range[.,u^. That is you can call RANDY (, ,a where i is a uniformly random integer chosen from I,..., u inclusive and as is the ID of the corresponding file. You solve the problem by doing something similar to binary search. You start by calling RANDY(1,n). Let's assume that Randy returns (i, a). You compare r to a. Ifyou found the file you were looking for. If a, you call RANDY(1,i -1) If >a you call RANDY(i +1,n) You continue recursive ly until you have either found the file or conclude that the file is not present in the evidence room. Show that the above algorithm accesses O(log n) files in expectation before it terminates. 2. With his trick in the previous question Randy was not able to slow you down very much. Now he decides to disallow "Tange" queries as above and only allows either sequential access to the files or access to a uniformly random file from the entire set. In particular, you now have two ways of accessing the list: By looking at a uniformly random element of the list. That is by calling RANDY() = ai, where i is chosen uniformly at random from 1, , n, inclusive Observe that you only receive the file ID, not the index of the file. This randomized binary search is in expectation roughly as fast as the usual deterministic one. . By asking Randy to give you the file directly following one he retumed to you in some previous call. For example if you first call RANDYO and get back a, you are allowed to call NEXT(a and get back at+1 Note that the list wraps around, so that NEXT(an) returns a1. Ifyou haven't already obtained a, in some previous call you may not call NEXT(a). To facilitate analyzing this setting, think of the files as being organized in the form of a circular sorted linked ist where every file points to the one with the next higher ID. (a) As a warm, let us analyze the following setting. You are given a circle of unit circumference. You pick k points on the circle independently and uniformly at random and snip the circle at those points, obtaining k different arcs. Determine the expected length of any single arc. Hint: Nate that the length of each arc is identically distributed, so each has the same expectation. What is the sum of their expectations?) (b) Develop a randomized algorithm for finding the file with ID r that makes at most O(Vn) calls to the functions NEXTO and RANDY in expectation and always returns the correct answer. Analyze the running time of the algorithm. A proof of correctness is Hint: Your algorithm will perform some random accesses and some amount of linear search Use pari (a) to analyze the number of steps in the linear search) not necessary You are a police officer trying to crack a case. You want to check whether an important file is in the evidence room. Files have IDs that are positive integers and the evidence room contains n files in sorted order of their IDs. Unfortunately, you do not have direct access to the evidence room; the only one who has access is Randy, who is corrupt and wants to make things hard for you. In the following we assume that r is the file ID you are looking for. I. You know that the evidence room is organized as a sorted list of n elements. If Randy was not corrupt you would probably do binary search by asking him to give you the median file of the list. Unfortunate ly, you can only give Randy two indices, u and he returns to you a file with index chosen uniformly at random from the range[.,u^. That is you can call RANDY (, ,a where i is a uniformly random integer chosen from I,..., u inclusive and as is the ID of the corresponding file. You solve the problem by doing something similar to binary search. You start by calling RANDY(1,n). Let's assume that Randy returns (i, a). You compare r to a. Ifyou found the file you were looking for. If a, you call RANDY(1,i -1) If >a you call RANDY(i +1,n) You continue recursive ly until you have either found the file or conclude that the file is not present in the evidence room. Show that the above algorithm accesses O(log n) files in expectation before it terminates. 2. With his trick in the previous question Randy was not able to slow you down very much. Now he decides to disallow "Tange" queries as above and only allows either sequential access to the files or access to a uniformly random file from the entire set. In particular, you now have two ways of accessing the list: By looking at a uniformly random element of the list. That is by calling RANDY() = ai, where i is chosen uniformly at random from 1, , n, inclusive Observe that you only receive the file ID, not the index of the file. This randomized binary search is in expectation roughly as fast as the usual deterministic one. . By asking Randy to give you the file directly following one he retumed to you in some previous call. For example if you first call RANDYO and get back a, you are allowed to call NEXT(a and get back at+1 Note that the list wraps around, so that NEXT(an) returns a1. Ifyou haven't already obtained a, in some previous call you may not call NEXT(a). To facilitate analyzing this setting, think of the files as being organized in the form of a circular sorted linked ist where every file points to the one with the next higher ID. (a) As a warm, let us analyze the following setting. You are given a circle of unit circumference. You pick k points on the circle independently and uniformly at random and snip the circle at those points, obtaining k different arcs. Determine the expected length of any single arc. Hint: Nate that the length of each arc is identically distributed, so each has the same expectation. What is the sum of their expectations?) (b) Develop a randomized algorithm for finding the file with ID r that makes at most O(Vn) calls to the functions NEXTO and RANDY in expectation and always returns the correct answer. Analyze the running time of the algorithm. A proof of correctness is Hint: Your algorithm will perform some random accesses and some amount of linear search Use pari (a) to analyze the number of steps in the linear search) not necessary