Randomized Algorithms
Exploring the Partition Theorem and Find-Min algorithm in the context of randomized incremental construction. Understand how to apply the theorem effectively and solve complex problems magically. Dive into the closest pair of points problem with deterministic and randomized algorithms. This content delves into mathematical exercises and notations related to the topic.
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 15 Randomized Incremental Construction (building the background) 1
Partition Theorem A set of events ?1, ,??defined over a probability space (?,P) is said to induce a partition of ? if ?=1 ?? = ? ?? ??= for all? ? ? B This theorem solves many difficult problems magically. But one needs some experience in order to apply it effectively. You will realize it soon. Partition Theorem: P(B) = ?P(B ??) ?P(B | ??) P(??) 2
PROBLEM 1 FIND-MIN PROBLEM 3
Find-Min algorithm Question: If elements of A are permuted randomly uniformly, what is the expected number of times variable ??? is updated ? Find-Min(A[1..?]) { ??? A[1]; For? = ? to ?do { if ( ?? ) ?? } return ???; } A[?] < ??? ??? A[?] ; ?: no. of times ??? is updated. ??= ? if??? is updated in ?th iteration ? otherwise ? = ? + ?>??? ? ? = ? + ?>??[??] = ? + ?>??(??= ?) ?? A 8 5 16 11 32 4 57 6 19 82 7 42 2 23 1 2 3 4 5 6 7 8 9 10 11 12 13 14 4
Find-Min algorithm First ? ?elements A ? ? ? 1 2 ?(??= ?) = Probability that A[?] is smaller than {A[?], , A[? ?]} Notations: ?? ?: set of all subsets of A of size ? ?. For any ? ?? ?, ??: first ? ?elements of A are (some permutation of) ?. Though this equation is perfectly correct, you won t be able to proceed from this point onwards to find ?(??= ?). Can you find the reason behind its uselessness ? Using Partition Theorem, ?(??= ?) = ? ?? ? ? ? ?(??= ?|??) ?(??) 5
PROBLEM 2 CLOSEST PAIR OF POINTS 6
Closest Pair of Points Problem Definition: Given a set ? of ? > ? points in plane, compute the pair of points with minimum Euclidean distance. Deterministic algorithms: O(??) : Trivial algorithm O(? ??? ?) : Divide and Conquer based algorithm Randomized algorithm: O(?) : Randomized Incremental Construction based algorithm 7
Notations and assumptions Notations: ? : set of ? points in plane. Coordinates of each point are positive integers. distance(?,?) : Euclidean distance between ? and ?. Assumption: Distance between each pair of points is distinct. 8
A discrete math exercise Exercise: What is the maximum number of points that can be placed in a unit square such that the minimum distance is at least 1 ? Answer: 4. If there are more than 4 points, at least one of the four small squares will have more than 1 points. 1 2 1 This exercise is used is deterministic algorithm as well the randomized algorithm that we shall discuss now. 9
Overview of the randomized algorithm starts with a set of 2 points, computes their distance; inserts 3rd point and updates the closest pair distance; inserts 4th point and updates the closest pair distance; Uses an efficient data structure, called Grid, to facilitate efficient processing during ith step: - To determine if ith point is going to change the closest pair distance. Incremental algorithm: 10
Grid(?,?) A data structure ? with operations: Locate_cell(?,?): Locates the cell to which ? belongs. ? Report all points belonging to cell ?. Report_points(?,?): Insert point ? in grid ?. Insert_point(?,?): ? Build grid for? with parameter?. Build_Grid(?,?): ? : set of points ? : distance between closest pair of points in ?. 11
Grid(?,?) The following time bounds are possible. Height Balanced Binary search tree Dynamic hashing Locate_cell(?,?) ?(??? |?|) ?(1) Report_points(?,?) ?(??? |?|) ?(1) Insert_point(?,?) ?(??? |?|) ?(1) expected Build_Grid(?,?) ?( ? ??? |?|) ?( ? ) expected Excluding Insert_point()operation, show as a homework, that we can achieve all other bounds using static hashing discussed in this course. 12
Closest Pair of Points Closest-pair-algorithm(?) Let <??,??, ,?? > be a uniformly random permutation of ?; ?? distance(??,??); Build_Grid(??,{??,??}); For? = ? to ? do { Step 1: locate the cell of the grid ?? ? containing ??; Step 2: find the point ? {??, ,?? ?} closest to ??; let ? = distance(?, ??); Step 3: If? > ?? ? ?? ?? ?; Insert(??,?? ?); Else ?? ?; ? Build_Grid(?,{??, ,??}); } return ??; 13
?th iteration ?? ? ?? We just need to insert ?? ?? ? 14
?th iteration ?? ? ?? We need to rebuild the grid ?? ? ?? 15
?th iteration ?? ?? ?? 16
Analysis of ?th iteration Closest-pair-algorithm(?) Let <??,??, ,?? > be a uniformly random permutation of ?; ?? distance(??,??); Build_Grid(??,{??,??}); For? = ? to ? do { Step 1: locate the cell of the grid ?? ? containing ??; Step 2: find the point ? {??, ,?? ?} closest to ??; let ? = distance(?, ??); Step 3: If? > ?? ? ?? ?? ?; Insert(??,?? ?); Else ?? ?; ? Build_Grid(?,{??, ,??}); } return ??; O(1) O(1) O(1) ?? for constant ? 17
running time of ?th iteration ??: running time of ?th iteration E[??] = ?? O(1) + ?? ?(??< ?? ?) Question: What is ?(??< ?? ?) ? ?(??< ?? ?) depends upon ?? ? which depends upon the first ? ? points. So we need to use Partition theorem to calculate ?(??< ?? ?). 18
Calculating ?(??< ???) Notations: ?? ?: set of all subsets of ? of size ? ?. ??: first ? ? points are (some permutation of) ?. For any ? ?? ?, ?(??< ?? ?) = ? ?? ? ? ? ?(??< ?? ?|??) ?(??) Though this equation is perfectly correct, you won t be able to proceed from this point onwards to find ?(??< ?? ?) Can you find the reason behind its uselessness ? 19
Homework Exercise Investigate the cause of problem in our forwardanalysis for each of the two problems. I am hopeful that at least one of you will reinvent this technique on his/her own before next class. (Backward analysis ) Try to find alternate approach for analysis. Provide efficient implementation of Grid data structure. 20
