CS 577: Intro. to Algorithms Lecture 15 New Topic: Randomized Algorithms • So far we’ve seen deterministic algorithms: • For a given input, the output was always the same and the runtime was always...

So far we’ve seen deterministic algorithms: • For a given input, the output was always the same and the runtime was always the same • Two types of Randomized Algorithms: 1. Always correct, but different runs of the program take different time 2. Always fast, but sometimes may output incorrect or inaccurate answers • Importantly, these guarantees must be for any given input. Randomness is in the choices of the algorithm and not in the input.


CS 577: Intro. to Algorithms Lecture 15 New Topic: Randomized Algorithms • So far we’ve seen deterministic algorithms: • For a given input, the output was always the same and the runtime was always the same • Two types of Randomized Algorithms: 1. Always correct, but different runs of the program take different time 2. Always fast, but sometimes may output incorrect or inaccurate answers • Importantly, these guarantees must be for any given input. Randomness is in the choices of the algorithm and not in the input. Goal: bound the expected runtime, example quicksort Goal: bound the probability of returning an incorrect answer Why randomness? • Usually simpler algorithms than deterministic ones • Faster in return for some accuracy loss or unpredictability • Load balancing or breaking symmetry • Hedging against unknown parameters Contention Resolution • n machines try to access a single resource • Example: n laptops sending a request over the internet at the same router • Break up timeline into steps • A step is successful if only one machine tries to access the resource • Goal: design an algorithm to coordinate machines so that there are no collisions • A simple algorithm: Each machine flips a coin and with probability p tries to access the resource • Run this protocol for t steps and give up if not successful. Probability Facts • Probability that event A happens • Pr[A] with 0 ≤ Pr[A] ≤ 1 • Inclusion-Exclusion • Pr[A∪B] = Pr[A] + Pr[B] - Pr[A∩B] • A∪B means either A or B happens • A∩B means both A and B happen • Union Bound • Pr[A∪B] ≤ Pr[A] + Pr[B] • Law of total probability • If A and B cover the entire space • Pr[A∪B] = 1 • If A and B never occur together • Pr[A∩B] =0, Pr[A∪B] = Pr[A] + Pr[B] A B Probability Facts • Conditional Probability Pr[A|B] • Probability that A happens given that B happens • Pr[A∩B] = Pr[B] Pr[A|B] • Independence • Two events A and B are independent if the likelihood of A is not affected by whether B happened • Pr[A|B] = Pr[A] and • Pr[A∩B] = Pr[B] Pr[A] A B Contention Resolution Q1: What is the probability that only machine i will try to access the resource at the first step? • Event ?$: machine i tries to access the resource • Event ?%: machine i does not try to access the resource • We are interested in event ?' = ?$ ∩ ?' ∩ ⋯∩ ?$*' ∩ ?$+' ∩ ⋯∩ ?, • All these events are independent • Pr ?' = Pr ?$ ∏%0$ Pr ?% = ? 1 − ? ,*' • The ? that maximizes the above is ? = 1/? • For that value Pr ? = ' , 1 − ' , ,*' ≥ ' , ' 8 Contention Resolution Q2: What is the probability that machine i will succeed after t steps? • Event ?9: machine i succeeds in round t • We are interested in event ? = ?' ∪ ⋯∪ ?9 • Pr ̅? = Pr ;?' ∩ ⋯∩ ;?9 • The events are independent • Pr ̅? = ∏<='9><] ≤="" 1="" −="" '="" 8,="" 9="" •="" if="" =="" ⌈??⌉,="" pr="" ̅?="" ≤="" 1/?="" •="" if="" =="" 2="" log="" ,="" pr="" ̅?="" ≤="" 1/?i="" contention="" resolution="" q3:="" what="" is="" the="" probability="" that="" all="" machines="" will="" succeed="" after="" t="" steps="" for="" =="" 2="" log="" •="" event="" $:="" machine="" i="" fails="" after="" t="" rounds="" •="" we="" are="" interested="" in="" event="" =="" '="" ∪="" ⋯∪="" ,="" •="" the="" events="" are="" not="" independent:="" use="" union="" bound="" •="" pr="" ≤="" ∑$="" pr="" $="" ≤="" ,="" ,l=' , • Thus the probability that all machines succeed is at least 1 − ' ,="" random="" variables="" and="" expectations="" •="" a="" random="" variable="" is="" any="" variable="" that="" takes="" on="" random="" values.="" usually="" domain="" is="" integers="" or="" real="" numbers="" •="" an="" event="" is="" something="" that="" happens="" with="" some="" probability="" •="" a="" random="" variable="" is="" something="" that="" takes="" different="" values="" randomly="" •="" examples:="" •="" the="" running="" time="" of="" an="" algorithm="" •="" random="" variable="" •="" is="" the="" running="" time="" at="" most="" f(n)?="" •="" event="" •="" the="" cost="" of="" a="" solution:="" random="" variable="" •="" the="" algorithm="" produces="" a="" minimum="" cost="" solution:="" event="" random="" variables="" and="" expectations="" •="" for="" a="" random="" variable="" ,="" we="" define="" the="" expectation="" as="" the="" weighted="" average="" of="" its="" values="" •="" [?]="∑N" op="" qrstop="" pr[?="?]" •="" properties:="" +="" =="" +="" even="" if="" x="" and="" y="" are="" correlated="" proof:="" +="" =="" ∑n="" pr[?="?]" +="" ∑n="" pr="" =="" +="" =="" ∑n="" pr="" =="" +="" =="" +="" [?]="" •="" ≠="" [?]="" in="" general="" •="" equality="" holds="" if="" the="" variables="" are="" independent="" examples="" •="" expected="" value="" of="" die="" roll="" for="" a="" standard="" 6-sided="" die="" •="" expected="" total="" value="" for="" 2="" die="" rolls="" •="" expected="" #heads="" in="" 10="" tosses="" of="" a="" fair="" coin="" •="" expected="" #times="" to="" throw="" a="" fair="" coin="" until="" heads="" indicator="" random="" variables="" •="" for="" an="" event="" a="" we="" can="" define="" an="" indicator="" variable="" z="" that="" is="" 1="" if="" the="" event="" happens="" or="" 0="" if="" it="" doesn’t="" •="" [?]="Pr[?]" •="" for="" many="" events="" a1,a2,…,an="" we="" can="" compute="" the="" expected="" number="" of="" events="" that="" happen="" by="" taking="" the="" expected="" value="" of="" the="" sum="" of="" their="" indicator="" random="" variables="" z1,z2,…,zn="" •="" ∑$="" $="∑$" [?$]="∑$" pr[?$]="" problem:="" selection="" •="" given="" a="" list="" of="" distinct="" numbers,="" find="" the="" k-th="" smallest="" instance:="" [1,="" 5,="" 2,="" 4,="" 8,="" 7],="" k="3" •="" the="" third="" smallest="" number="" is="" 4.="" •="" simple="" strategy:="" sort="" the="" sequence="" and="" output="" the="" k-th="" smallest="" •="" runtime="" o(n="" log="" n)="" •="" can="" we="" do="" better?="" •="" when="" k="1" we="" can="" find="" the="" min="" in="" o(n)="" time.="" •="" can="" we="" find="" the="" median,="" i.e.="" k="n/2" in="" o(n)="" time?="" d&c="" algorithm="" for="" selection="" a:="" [8,="" 3,="" 20,="" 1,="" 9,="" 15,="" 18,="" 6,="" 2,="" 13,="" 11]="" a1:="" [3,="" 1,="" 6,="" 2]="" a2:="" [20,="" 9,="" 15,="" 18,="" 13,="" 11]="" pick="" a="" “pivot”="" element="" x,="" e.g.="" x="8" a[i]="">< x="" a[i]=""> x Goal: Given a list of numbers, find the k-th smallest k = 7 A2: [20, 9, 15, 18, 13, 11] k = 7-|A1|-1 = 2 8 Selection: Implementation Selection(Array A[1…n], k) • If n=1 Then Return A[1] • x ← Choose_Pivot(A) • A1 = [], A2 = [] • For i = 1 to n If A[i] < x="" then="" a1.insert(a[i])="" if="" a[i]=""> x then A2.insert(A[i]) • If k ≤ |A1| then Return Selection(A1, k) • Else If k > n – |A2| then Return Selection(A2, k –|A1| – 1) • Else Return x Correctness by induction on n Base case (n=1): • With a single element we can only have k=1 so returning A[1] is the solution Inductive hypothesis (assume correct up to n-1) Inductive step (correctness for n>1): • If k ≤ |A1| then the k-th smallest number is the k-th smallest in A1 as everything else is larger than x. As |A1| n – |A2| it means that the k-th smallest is not among the n – |A2| smallest numbers and thus is in A2, QuickSelect: Implementation QuickSelect(Array A[1…n], k) • If n=1 Then Return A[1] • x ← Random entry of A • A1 = [], A2 = [] • For i = 1 to n If A[i] < x="" then="" a1.insert(a[i])="" if="" a[i]=""> x then A2.insert(A[i]) • If k ≤ |A1| then Return QuickSelect(A1, k) • Else If k > n – |A2| then Return QuickSelect(A2, k – |A1| – 1) • Else Return x Running Time? Random variable What is the expected Running Time ? ? ≤^ $=' , 1 ? ? max ? − 1, ? − ? + ? ?(?) ≤ ^ $=,/I , 2 ? ? ? + ? Guess ? ? ≤ 4? Proof by induction • Base case: ? 0 = 0 • ? ? ≤ ∑$=,/I,*' I , ? ? + ? ≤ ∑$=,/I ,*' h$ , + ? • ? ? ≤ 3? + ? ≤ 4? QuickSelect: Alternate Analysis • Let Ai be the event that at step i we choose an element x such that the rank of x lies in [n/4, 3n/4] • Claim: the expected number of rounds i until Ai occurs is at most 2 • The probability that Ai occurs is at least 1/2 at every round • The expected number of executions is at most 2 (follows from the coin toss example) • Thus, we get the recurrence T(n) = T(3n/4) + O(n) which gives T(n) = O(n)
Jan 03, 2022
SOLUTION.PDF

Get Answer To This Question

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here