CSC3160: Design and Analysis of Algorithms Week 4: Randomized Algorithms Instructor: Shengyu Zhang 1
Instructor: Shengyu Zhang 1
Randomized Algorithms -We use randomness in our algorithms. You've seen examples in previous courses quick sort:pick a random pivot. We'll see more in this week. 2
Randomized Algorithms ◼ We use randomness in our algorithms. ◼ You’ve seen examples in previous courses ❑ quick sort: pick a random pivot. ◼ We’ll see more in this week. 2
Motivation Why randomness? Faster. Simpler. Price:a nonzero error probability Usually can be controlled to arbitrarily small. Repeating k times drops the error probability to c-k for some constant c>1. Second part of the lecture. 3
Motivation ◼ Why randomness? ❑ Faster. ❑ Simpler. ◼ Price: a nonzero error probability ❑ Usually can be controlled to arbitrarily small. ❑ Repeating 𝑘 times drops the error probability to 𝑐 −𝑘 for some constant 𝑐 > 1. ◼ Second part of the lecture. 3
General references RANDOMIZED Randomized Algorithms, LGORITHMS Rajeev Motwani and Prabhakar Raghavan,Cambridge University Press,1995. Probability and Computing, Probabitity and Computing Eotni pvelas mttobkaene boeh Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005. 4
General references ◼ Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995. ◼ Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005. 4
Part 1:Examples Example 1:Polynomial ldentity Testing 5
Part 1: Examples Example 1: Polynomial Identity Testing 5