| Course Outline | General Information | Study Material | Lectures (classwise) | Problems, Exams and Assignments (updated) |
The course consists of 4 lecture hours (2 classes of 2 hours each) per week.
The basic thrust of the course would be to study probability and stochastic processes and to learn their applications to computer science.
We will try to stick to the basic course outline as given in this page.
| Class Timings: | Tuesday 09:30-11:10, Thursday 09:30-11:10 NAB I |
| The necessary evil - marks, exam, etc.: | Mid-sem: 25, End-sem: 50, Internal evaluation: 25 |
| Books |
(B1) A First Course in Probability Sheldon Ross Pearson. (B2) Probability and Computing: Randomized Algorithms and Probabilistic Analysis Michael Mitzenmacher and Eli Upfal Cambridge. (B3) An Introduction to Probability Theory and its Applications: Volume I William Feller John Wiley & Sons. (B4) Introduction to Probability Theory P. G. Hoel, S. C. Port and C. J. Stone University Book Stall/Houghton Mifflin, New Delhi/New York. (B5) The Art of Computer Programming: Seminumerical Algorithms, Vol. 2 Donald E. Knuth Pearson (B6) Invitation to Discrete Mathematics J. Matousek and J. Nesetril Clarendon Press, Oxford (B7) Applied Combinatorics Fred S. Roberts and B. Tesman Pearson, Prentice Hall (B8) Introduction to Probability Dimitri P. Bertsekas and John N. Tsitsiklis Athena Scientific, Massachusetts (B9) Algorithm Design J. Kleinberg and E. Tardos Pearson (B10) The Probabilistic Method Noga Alon and Joel H. Spencer Wiley (B11) Proofs from THE BOOK Martin Aigner and Gunter M. Ziegler Springer (B12) Counting: The Art of Enumerative Combinatorics George E. Martin Springer |
| Web Resources |
(W1) Richard Weber's course on Probability for first year mathematicians at Cambridge
|
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (23-07-19) |
Introductory lecture: Motivating probability applications in CS: median finding | -- | Chapter 13 in (B9) |
| Lecture 2 (25-07-19) |
Probability and its uses in CS: a randomized analysis of quicksort | -- | Chapter 7 in (B1), Chapter 2 in (B2), Chapter 13 in (B9) |
| Lecture 3 (30-07-19) |
Principle of inclusion and exclusion: Counting derangements, onto functions Counting (in)distinguishable balls in (in)distinguishable bins with boxes empty or not empty |
-- | Chapters 1 and 2 in (B12) |
| Lecture 4 (01-08-19) |
Introduction to probability and its axioms; Boole's inequality; Inclusion-Exclusion Formula; probability of derangement |
-- | Chapter 1 in (B8), Chapter 4 in (W1) |
| Lecture 5 (06-08-19) |
Birthday problem, Probabilistic method: existence of non-monochromatic edge colored subgraph Continuous models in probability, Principle of inclusion and exclusion, Bonferroni's inequality |
-- | Chapter 1 in (B8), Chapter 4 in (W1) |
| Lecture 6 (08-08-19) |
Conditional probability; multiplication rule; Total probability theorem Derangement (again!) |
-- | Chapter 1 in (B8), Chapter 6 in (W1) |
| Lecture 7 (13-08-19) |
Gambler's ruin; Bayes' Theorem; Independence and mutual independence of a collection of events; | -- | Chapter 1 in (B8), Chapters 4 and 5 in (W1) |
| Lecture 8 (20-08-19) |
Independent trials and binomial; Conditional independence; Using a biased coin to make an unbiased choice; Problem of points; Laplace's rule of succession. |
-- | Chapter 1 in (B8), Chapters 5 and 6 in (W1) |
| Lecture 9 (22-08-19) |
Discrete random variables and expectation; independence and mutual independence of random variables Linearity of expectation; Bernoulli trials; Geometric random variable and waiting for success bound |
-- | Chapter 2 in (B8), Chapter 7 in (W1) |
| Lecture 10 (27-08-19) |
Function of a random variable; Jensen's inequality PMF and CDF; Memoryless property of geometric random variable; Properties of Expectation; |
-- | Chapter 2 in (B8), Chapter 7 and 8 in (W1) |
| Lecture 11 (29-08-19) |
Variance, Covariance; Variance of sum of random variables | -- | Chapter 2 in (B8), Chapter 9 in (W1) |
| Lecture 12 (03-09-19) |
Derangement, Birthday problem, Balls and bins and Poisson; Uniform distribution; Negative binomial and hypergeometric distribution |
-- | Chapter 2 in (B8), Chapters 8 and 9 in (W1) |
| Lecture 13 (05-09-19) |
Sum of independent Poisson and Binomial; Upper bound on variance for bounded random variable; Concentration inequality: Markov and Chebyshev |
-- | Chapters 2 and 5 in (B8), Chapter 11 in (W1) |
| Lecture 14 (17-09-19) |
Joint PMFs of multiple random variables; Conditional PMF | -- | Chapter 2 in (B8) |
| Lecture 15 (18-09-19) |
Total expectation theorem; Conditional Expectation |
-- | Chapter 2 in (B8), Chapter 13 in (W1) |
| Lecture 16 (19-09-19) |
Branching Process; Independence of a random variable from an event; independence of random variables; Sample mean and variance |
-- | Chapter on Conditional Expectation in (B2) for birth process, the rest from Chapter 2 in (B8) |
| Lecture 17 (15-10-19) |
Continuous random variable, PDF, CDF | -- | Chapter 3 in (B8) |
| Lecture 18 (16-10-19) |
Continuous random variable, PDF, CDF | -- | Chapter 3 in (B8) |
| Lecture 19 (17-10-19) |
Moment generating function and Chernoff bounds | -- | Chapter 4 in (B2) |
| Lecture 20 (22-10-19) |
Chernoff bounds | -- | Chapter 4 in (B2) |
| Lecture 21 (23-10-19) |
Parameter estimation and Chernoff bounds; Normal distribution and its expectation and variance |
-- | Chapter 4 in (B2); Chapter 3 in (B8) |
| Lecture 22 (24-10-19) |
Derived distribution, PDF of a linear function of a random variable Standard normal random variable; MGF and its use in finding the PDF of sum of independent random variables |
-- | Chapter 4 in (B8) |
| Lecture 23 (31-10-19) |
Weak Law of Large Numbers and its applications | -- | Chapter 5 in (B8), Chapter 8 in (B1) |
| Lecture 24 (02-11-19) |
Central Limit Theorem | -- | Chapter 5 in (B8), Chapter 8 in (B1) |
| Lecture 25 (03-11-19) |
Strong Law of Large Numbers | -- | Chapter 5 in (B8), Chapter 8 in (B1) |
| Lecture 26 (04-11-19) |
Introduction to Stochastic Process; Markov Chains |
-- | Chapter 7 in (B2), Chapter 7 in (B8) |
| Problems | POSTED ON | SOLUTIONS |
| Problem Sheet 1 | August 10, 2019 | Discussed by Gopinath on 14/8/19 |
| Problem Sheet 2 | August 27, 2019 | Discussed by Gopinath on 28/8/19 |
| Problem Sheet 3 | September 5, 2019 | Discussed by Gopinath on 05/9/19 |
| Problem Sheet 4 | ---- | Discussed by Gopinath on 29/10/19 |
| Class Tests | Date, Time and Venue | SOLUTIONS |
| Class Test I | September 4, 2019; 11:30 am, Room 716-717 | Solutions |
| Mid Sem | September 9, 2019 | Solutions |
| Class Test II | October 30, 2019; 11:00 am ~ 12:00 noon; Room 716-717 | Solutions |
| Class Test III | November 15, 2019; Room 716-717 | Solutions |