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)