Course Info 。尹一通 yitong.yin@gmail.com yinyt@nju.edu.cn 。office hour: 804,Thursday 2-4pm course homepage:http://tcs.nju.edu.cn/wiki
Course Info • 尹一通 yitong.yin@gmail.com yinyt@nju.edu.cn • office hour: 804, Thursday 2-4pm • course homepage: http://tcs.nju.edu.cn/wiki
Textbooks ITHMS Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press,1995. Probability and Computing tandomized Algorithms and Probabilistic Analysis Michael Mitzenmacher EhUp国 Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press,2005
Textbooks Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995. Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005
References 有件海世A3转：C时N CHAILE1年.BB6n k0NA10。v4n7 CLIFFOND STEIN CLRS Feller INTRODUCTION TO ALGORITHMS An Introduction to Probability Theory and Its Applications 生WLE到 Aldous and Fill Reversible Markov Chains and THE PROBABILISTIC Random Walks on Graphs HETHOD Third Editiee Alon and Spencer The Probabilistic Method
References CLRS Feller An Introduction to Probability Theory and Its Applications Aldous and Fill Reversible Markov Chains and Random Walks on Graphs Alon and Spencer The Probabilistic Method
Randomized Algorithms 'algorithms which use randomness in computation 44 Turing Machine random coin Why? Simpler. ● Faster. ● Can do impossibles. ● Can give us clever deterministic algorithms. ● Random input. ● Deterministic problem with random nature
“algorithms which use randomness in computation” Randomized Algorithms Why? • Simpler. • Faster. • Can do impossibles. • Can give us clever deterministic algorithms. • Random input. • Deterministic problem with random nature. • ... ... Turing Machine random coin
Checking Matrix Multiplication three nxn matrices A,B,C: A X B 是 C best matrix multiplication algorithm:O(n2.373)
Checking Matrix Multiplication A × B = C ? three n×n matrices A, B, C: best matrix multiplication algorithm: O(n2.373)
Checking Matrix Multiplication three nxn matrices A,B,C: 3.0 na ve 兰 C 2.9 人 O(n) Strassen 2.8 PaⅫ Bini et al. 2.7 gorithm:O(n2.373) 2.6 Schonhage Romani 2.5 Coppersmith,Winograd Strassen 2.4 Coppersmith,Winograd Stothers Williams Year 1950 1960 1970 1980 1990 2000 2010
Checking Matrix Multiplication A × B = C ? three n×n matrices A, B, C: best matrix multiplication algorithm: O(n) O(n2.373)
Checking Matrix Multiplication three nxn matrices A,B,C: A X B 是 C best matrix multiplication algorithm:O(n2.373) Freivald's Algorithm pick a uniform random r E0,1)"; check whether A(Br)=Cr; time:O(n2) if AB =C,always correct
best matrix multiplication algorithm: Checking Matrix Multiplication A × B = C ? three n×n matrices A, B, C: Freivald’s Algorithm pick a uniform random r ∈{0,1}n; check whether A(Br) = Cr ; time: O(n2) if AB = C, always correct O(n2.373)
Freivald's Algorithm pick a uniform random r∈{0，l"; check whether A(Br)=Cr; if AB =C,always correct ifAB≠C, letD=AB-C≠0n×n sayD,卡0 2n1 1 PABr-C1-PD.s 2 二 -2 m (Dr)i=>Dikrk =0 D r k=1 i ∑D >=D k≠j
Freivald’s Algorithm pick a uniform random r ∈{0,1}n; check whether A(Br) = Cr ; if AB = C, always correct if AB ≠ C, Pr[ABr = Cr] = Pr[Dr = 0] let D = AB C = 0nn D r i (Dr)i = n k=1 Dikrk =0 rj = 1 Dij n k=j Dikrk 2n 2n1 = 1 2 say Dij = 0
Freivald's Algorithm pick a uniform random r∈{0，l"; check whether A(Br)=Cr; if AB =C,always correct Theorem(Freivald,1979) IfAB≠C,for a uniformly random r∈{0,1n, 1 Pr[ABr=Cr]≤ repeat independently for 100 times time:O(n2) ifAB≠C,error probability≤2-1oo
Freivald’s Algorithm pick a uniform random r ∈{0,1}n; check whether A(Br) = Cr ; if AB = C, always correct If AB ⇥= C, for a uniformly random r {0, 1}n , Pr[ABr = Cr] 1 2 . Theorem (Freivald, 1979) repeat independently for 100 times time: O(n2) if AB ≠ C, error probability ≤ 2100
Monte Carlo ys Las Vegas Two types of randomized algorithms: Monte Carlo Las Vegas LAS VEGAS N E VA DA running time is fixed always correct correctness is random running time is random
Monte Carlo vs Las Vegas Monte Carlo Las Vegas running time is fixed correctness is random always correct running time is random Two types of randomized algorithms: