Applications and Insights into Randomized Algorithms
Discover the application of fingerprinting techniques and 1-dimensional pattern matching in randomized algorithms. Learn about designing randomized algorithms based on random ideas, insight into problems, and the role of randomization in materializing ideas. Explore topics such as Randomized Quick Sort, Approximate Median, and more in the field of Randomized Algorithms.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Randomized Algorithms CS648 Lecture 6 Reviewing the last 3 lectures Application of Fingerprinting Techniques 1-dimensional Pattern matching Preparation for the next lecture. 1
Randomized Algorithms discussed till now Randomized algorithm for Approximate Median Randomly select a sample Randomized Quick Sort Randomly permute the array Frievald s algorithm for Matrix Product Verification Randomly select a vector Randomized algorithm for Equality of two files Randomly select a prime number 2
Randomized Algorithms How does one go about designing a randomized algorithm ? 3
Randomized Algorithms Some random idea is required to design a randomized algorithm. 4
Randomized Algorithms An idea based on insight into the problem Difficult/impossible to exploit the idea deterministically Randomization to materialize the idea A randomized algorithm 5
Randomized Quick Sort ? ? A Elements of A arranged in Increasing order of values pivot ?? ? ? ? 7
Randomized Quick Sort Observation: There are many elements in A that are good pivot. Is it possible to select one good pivot efficiently ? (not possible deterministically ) A randomly selected element is a good pivot with probability 1 2 We select pivot element randomly uniformly. 8
RANDOMIZED ALGORITHM FOR APPROXIMATE MEDIAN 9
Randomized Algorithm for Approximate median A sample captures the essence of the original population. 10
Randomized Algorithm for Approximate median Idea: Is it possible to select a small subset of elements whose median approximates the median ? (not possible deterministically ) A random sample captures the essence of the original population. Median of a uniformly random sample will be approximate median. 11
FRIEVALDS TECHNIQUE APPLICATION MATRIX PRODUCT VERIFICATION 12
FrievaldsAlgorithm 1 0 1 1 0 ? ? ? ? 1 0 1 1 0 ? ? ? 13
FrievaldsAlgorithm The key idea Fact: An equation ?? + ? = 0 has a unique solution depending upon ? and ? only. Problem:Suppose you do not know the values of ? and ?. Your aim is to select a value for ? which does not satisfy the corresponding equation. Idea: Consider any two different values {?1, ?2}. Surely the equation is not satisfied for at least one of {?1, ?2}. Can we select that value deterministically ? Randomization used to exploit the idea: ? selects a value randomly uniformly out of {?1, ?2}. 14
FrievaldsAlgorithm (Analyzing error probability) 1 2 ? 1 2 ??1 ?1 + ??2 ?2 + ??? ?? = 0 Fixing the values of ?2, ,?? arbitrarily ? ? = (? ? ?) ? ??1 ?1 + ??2 ?2 + ??? ?? = 0 15
FINGERPRINTING APPLICATION CRYPTOGRAPHY 16
File A File B Aim: To determine if File A identical to File B by communicating fewest bits ? 17
How many primes less than ? ? ? Primes less than ? 100 25 1000 168 10000 1229 100000 9592 1000000 78498 ? ? log ? 18
Key idea from prime 2? ? 1 Less than ? prime factors of ? 4?2log? 1 around ?2prime numbers in [1,4?2log?] 19
Visualize a file as a binary number File A = ?0 ?1 ?2 ?? 1 File B = ?0 ?1 ?2 ?? 1 ? 12? ?? ? 12? ?? < 2? ?A= ?=0 ?B= ?=0 < 2? Overview of Protocol: Let ? be a prime number selected randomly uniformly from [2,?2log?] If?A mod ? = ?B mod ?then conclude A=B else conclude A B Error occurs if ? isone of the prime factors of(?A ??) 20
FINGERPRINTING APPLICATION 3 PATTERN MATCHING 21
17 Text ?[0 ? 1]: Pattern ?[0 ? 1]: 100101100110001101111010101110101010111010000101 011110101011101 Pattern ? is said to appear in Text ? at location ? if ? ? + ? = ?[?] for all 0 ? < ?. Problem: Given a Text ?[0 ? 1], and a pattern ?[0 ? 1], does ?appear anywhere in ? ? Deterministic Algorithm Trivial algorithm: O(??) time Knuth-Morris-Pratt algorithm: O(? + ?) time Randomized Monte Carlo Algorithm O(? + ?) time, and error probability < 1 ?? 22
Motivation Simplicity, real time implementation, streaming environment Extension to 2-dimensions 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 m m n n O(??+ ??) time algorithm Converting Monte Carlo to Las Vegas algorithm 23
RANDOMIZED ALGORITHM FOR FINGERPRINTING 24
Checking if ? appears in Text ? at location ? ? Text ?[0 ? 1]: Pattern ?[0 ? 1]: 100101100110001101111010101010101010111010000101 0111101110110101 Observation: O(?) time algorithm is obvious. Question: How to do this task in O(1) time ? Answer: have a fingerprint . Question: What properties should the fingerprint possess? ?? ?? Efficiently computable Small size 25
Checking if ? appears in Text ? at location ? ? Text ?[0 ? 1]: Pattern ?[0 ? 1]: 100101100110001101111010101010101010111010000101 0111101110110101 ? 12? 1 ? ?[?] ? 12? 1 ? ?[? + ?] ?? = ?=0 ??(?) = ?=0 Let ? be a prime number selected randomly uniformly from [2,? ] ??? = ??(?) mod ?. ??= ?? mod ?. If??? =??then conclude that ? appears at ?. Error occurs if ? isone of the prime factors of(?A ??) Error probability at location ? ?(?) Fingerprint has size= O(log?) bits. ? Small size but Not efficiently computable 26
Checking if ? appears in Text ? at location ? ??(? + 1) ? Text ?[0 ? 1]: Pattern ?[0 ? 1]: 100101100110001101111010101010101010111010000101 0111101110110101 ??(?) ? 12? 1 ? ?[?] ? 12? 1 ? ?[? + ?] ?? = ?=0 ??(?) = ?=0 Question: Any relation between ??(?) and ??(? + 1) ? Question: Any relation between ??(?) and ??(? + 1) ? ??(? + 1) = ??? 2? 1 ? ? ??(? + 1) mod ? = ( ??? 2? 1 ? ? ??(? + 1) = ( ??? 2? 1 ? ? ??(? + 1) = ( ??? (2? 1mod?) ? ? 2 + ? ? + ? 2 + ? ? + ?)mod? 2 + ? ? + ?)mod? 2 + ? ? + ?)mod? < ? 27
Fingerprint function: how good is it ? ? Text ?[0 ? 1]: Pattern ?[0 ? 1]: 100101100110001101111010101010101010111010000101 0111101110110101 ? 12? 1 ? ?[?]mod? ? 12? 1 ? ?[? + ?]mod? ?? = ?=0 ??(?) = ?=0 Lemma: The fingerprint function Occupies ??? ?bits. Computing take O(??? ?) bits operations. Error probability for any particular location is ? ?(?). Question: What is the error probability of the algorithm ? 28
Bounding the error probability of the algorithm ?: event that the algorithm fails ?? : event that the fingerprint shows a false match at any fixed location ? Can you see some relation between ? and ?? s ? ? = ??? P(?) ? ?(??) = (? ?)?(??)since?(??)is the same for each ?. <??(??) = ? ?(?). ? Question: How large should ? be to ensure P(?) < ? 2 Answer: ? = ?(?3?log?) Fingerprint size: O(log?). 29
Final result Theorem: There is a Monte Carlo randomized algorithm for detecting any match of P[0 ? 1] in T[0 ? 1] that : Fails with error probability < ? 2. Performs O(? + ?) operations involving O(log ?) bit numbers. It takes O(1) time on word-RAM model of computation for an operation involving O(log ?) bit numbers. So the time complexity of the algorithm is O(? + ?) Homework: It is possible to convert the above algorithm to Las Vagas. Spend some time thinking over it (we shall discuss it in some class). 30
Probability tool (union theorem) Suppose there is an event ? defined over a probability space (?,P). Aim: to get an upper bound on P(?). If it is difficult to calculate P(?), try to express ? as union of ? events ??(usually similar/same) such that it is easy to calculate P(??) Then you may bound P(?) using the following inequality: P(?) ??(??) 31
APPLICATIONS OF THE UNION THEOREM 32
Balls into Bins 1 2 3 4 5 m-1 m 1 2 3 i n Ball-bin Experiment: There are ? balls and ? bins. Each ball selects its bin randomly uniformly and independent of other balls and falls into it. Used in: Hashing Load balancing in distributed environment 33
Balls into Bins 1 2 3 4 5 m-1 m 1 2 3 i n Ball-bin Experiment: There are ? balls and ? bins. Each ball selects its bin randomly uniformly and independent of other balls and falls into it. Theorem: For the case when ? = ?, prove that with very high probability, every bin has O(log?) balls. (The proof requires Union theorem and elementary probability. We shall discuss it in the next class. Spend some time to prove it on your own.) 34
Randomized Quick sort Theorem: Probability that Randomized Quick sort performs more than 8 ? log? comparisons is less than ? 2. Tools needed: 1. Union theorem 2. Probability that we get less than ? HEADS during 8? tosses of a fair coin is less than (3 4)8?. (The proof requires Union theorem and elementary probability. We shall discuss it in the next class. Spend some time to prove it on your own.) 35
