Course Objective
To introduce the power of probability theory and randomization techniques in computer science, with particular emphasis on analyzing algorithms that employ randomization.
Course Contents
Introduction (3 lectures) : Axioms of Probability, Events, Some Basic Applications : Verifying Polynomial Identities, Karger’s Randomized Min-cut Algorithm.
Random Variables and Expectation (6 lectures): Linearity of Expectations, Jensen’s Inequality, Bernoulli and Binomial Random Variables, Conditional Expectation, Geometric Distribution, Coupon Collector’s Problem, Expected Run-Time of Quicksort.
Moments and Deviations (9 lectures) : Markov’s Inequality, Variance and Moments of a Random Variable, Chebyshev’s Inequality, Application to Problems like Coupon Collector’s Problem and Randomized Median Computation, Moment Generating Functions, Chernoff Bounds for the Sum of Poisson Trials, Applications like Parameter Estimation and Set Balancing.
Balls, Bins, and Random Graphs (6 lectures) : Birthday Paradox, The Balls-and-Bins Model, Applications to Bucket Sort and Chain Hashing, Random Graph Models and Application to Hamiltonian Cycles in Random Graphs.
Probabilistic Method (9 lectures) : Basic Counting Argument, Expectation Argument with Applications to Finding a Large Cut and Maximum Satisiability. Derandomization Using Conditional Expectations, Sample and Modify Technique with Applications to Independent Sets and Graphs with Large Girth.
A subset of advanced topics (9 lectures) like Markov Chains: Definitions and Representations, Randomized Algorithms for 2-Satisfiability and 3-Satisfiability, Classification of States, The Gambler’s Ruin, Stationary Distributions, Random Walks on Undirected Graphs, Application to s–t Connectivity, The Monte Carlo Method and Application to DNF Counting or
Pairwise Independence and Universal Hash Functions : Pairwise Independence, Construction of Pairwise Independent Bits and Application to Derandomization of an Algorithm for Large Cuts, Construction of Pairwise Independent Values Modulo a Prime, Chebyshev’s Inequality for Pairwise Independent Variables, Sampling Using Fewer Random Bits, Universal Families of Hash Functions, Perfect Hashing.
Learning Outcomes
Students will be able to model probabilistic events using random variables and analyze simple probabilistic algorithms using probabilistic tools acquired in this course.
Learning Objective
To introduce the power of probability theory and randomization techniques in computer science, with particular emphasis on analyzing algorithms that employ randomization.
Textbooks
- Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, Michael Mitzenmacher and Eli Upfal, Cambridge University Press; 2nd edition, 2017, ISBN-13 : 978-1107154889.
Reference Books
- Randomized Algorithms by Motwani and Raghavan, Cambridge University Press, 1995, ISBN-13: 978-0521474658.
- The Probabilistic method, by Alon and Spencer, 3rd edition, Wiley, 2008, ISBN 978-0-470-17020-5.
Past Offerings
- Offered in Jan-May, 2023 by Deepak Rajendraprasad
- Offered in Jul-Dec, 2021 by Satyadev (CSE, IITK)
- Offered in July-Dec, 2017 by John Augustine (CSE, IITM)
Course Metadata
| Item | Details |
|---|---|
| Course Title | Probability and Computing |
| Course Code | CS5820 |
| Course Credits | 3-0-0-3 |
| Course Category | PME |
| Proposing Faculty | Jasine Babu & Krithika Ramaswamy |
| Approved on | Senate 14 of IIT Palakkad |
| Course prerequisites | NIL |
| Course status | revised |
| Course revision information | Replacement of a 4 credit course with the same title and course code |