Denote t = |S∩T|, for all t elements in |S∩T| we will get a positive result, the probability that we get a positive result for each of the m-t elements in |S\T| is ~ (1-e) and thus the probability of getting a positive result for all these m-t elements and so returning a TRUE ⊈ answer although S T is ~ (1-e) Note that the above analysis (b and c) gives an estimation of average run time Question 4 You are given an array A[1..n] with n distinct real numbers and some value X. You need to determine whether there are two numbers in A[1..n] whose sum equals X. Do it in deterministic O(nlogn) time. Do it in expected O(n) time. Solution a: Sort A (O(nlogn) time). Pick A[1]. Perform a binary search (O(logn) time) on A to find an element that is equal to X-A[1]. If found, you’re done. Otherwise, repeat the same with A[2], A[3], … Overall O(nlogn) time Solution b: Choose a universal hash function from a universal collection of hash functions h H. Store all elements of array A in a of size using and chaining. Hash table n h For (i = 1; i <= n; i++) { If ((A[i] is in && (X-A[i] is in { Table) Table)) Return true } Return false Time Complexity: We don't know if the elements inside the array distribute randomly. If they do not distribute randomly then using a "regular" hash function can result in and then the runtime could = O(n) α be O(n^2). If we use a function then regardless of the keys distribution the probability that two keys universal hash collide is no more than As seen in class if we use chaining and a function then 1/m = 1/n. universal hash the expected search time is and the expected runtime for the algorithm is O(1) O(n). Question 5 - Rolling hash
Denote t = |S∩T|, for all t elements in |S∩T| we will get a positive result, the probability that we get a positive result for each of the m-t elements in |S\T| is ~ (1-e) and thus the probability of getting a positive result for all these m-t elements and so returning a TRUE answer although S ⊈ T is ~ (1-e) Note that the above analysis (b and c) gives an estimation of average run time Question 4 You are given an array A[1..n] with n distinct real numbers and some value X. You need to determine whether there are two numbers in A[1..n] whose sum equals X. Do it in deterministic O(nlogn) time. Do it in expected O(n) time. Solution a: Sort A (O(nlogn) time). Pick A[1]. Perform a binary search (O(logn) time) on A to find an element that is equal to X-A[1]. If found, you’re done. Otherwise, repeat the same with A[2], A[3], … Overall O(nlogn) time Solution b: Choose a universal hash function h from a universal collection of hash functions H. Store all elements of array A in a Hash table of size n using h and chaining. For (i = 1; i <= n; i++) { If ((A[i] is in Table) && (X-A[i] is in Table)) { Return true } Return false Time Complexity: We don't know if the elements inside the array distribute randomly. If they do not distribute randomly then using a "regular" hash function can result in α = O(n) and then the runtime could be O(n^2). If we use a universal hash function then regardless of the keys distribution the probability that two keys collide is no more than 1/m = 1/n. As seen in class if we use chaining and a universal hash function then the expected search time is O(1) and the expected runtime for the algorithm is O(n). Question 5 - Rolling hash
new_hash_ps8.docx