| 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, but may deviate a bit.
| 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 |
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (17-07-18) |
A primer on counting: (in)distinguishable balls in (in)distinguishable bins | -- | -- |
| Lecture 2 (19-07-18) |
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 (24-07-18) |
Probability and its uses in CS: a randomized analysis of median finding | -- | Chapter 13 in (B9) |
| Lecture 4 (26-07-18) |
Introduction to probability and its axioms | -- | Chapter 2 in (B1), Chapter 1 in (B8) |
| Lecture 5 (02-08-18) |
Probability of union of events; Bonferroni's inequality; Birthday problem; Derangement/Matching problem | -- | Chapter 2 in (B1), Chapter 1 in (B8), Chapter II in (B3) |
| Lecture 6 (07-08-18) |
Conditional probability; multiplication rule Conditional probability: an example using min-cut in undirected graphs |
-- | Chapter 1 in (B8), Chapter 1 in (B3), Chapter 13 in (B9) |
| Lecture 7 (08-08-18) |
Conditional probability: an example using min-cut in undirected graphs Total probability theorem; Bayes' theorem |
-- | Chapter 1 in (B3), Chapter 13 in (B9); Chapter 3 in (B1), Chapter 1 in (B8) |
| Lecture 8 (14-08-18) |
Independence of a collection of events; independent trials and binomial Conditional independence |
-- | Chapter 1 in (B8); Chapter 3 in (B1) |
| Lecture 9 (16-08-18) |
Gambler's ruin and derangement (conditional probability) | -- | Chapter 3 in (B1); Chapter 1 in (B8) |
| Lecture 10 (21-08-18) |
Derangement (conditional probability); non-existence of monochromatic clique (probabilistic method) Probability as a continuous set function |
-- | Chapter 3 in (B1); Chapter 1 in (B10); Chapter 1 in (B8) |
| Lecture 11 (23-08-18) |
Using a biased coin to make an unbiased decision Problem of points, Laplace's rule of succession Random variables and expectation |
-- | Chapters 3 and 4 in (B1); Chapters 1 and 2 in (B8) |
| Lecture 12 (28-08-18) |
Linearity of expectation; Expectation of a function of a random variable; Jensen's inequality; Moments and variance; Bernoulli trials; Geometric random variables -- waiting for the first success bound, Coupon collector's problem |
-- | Chapter 4 in (B1); Chapter 2 in (B8); |
| Lecture 13 (29-08-18) |
Variance, Covariance; variance of the sum of a finite number of random variables; expectation of a independent random variables; Geometric random variable, Binomial random variable, Poisson random variable |
-- | Chapter 4 in (B1); Chapter 2 in (B8), Chapter 2 in (B2); |
| Lecture 14 (30-08-18) |
Poisson approximation for Binomial; discrete uniform distribution Markov and Chebyshev's inequality |
-- | Chapter 2 in (B8); Chapter 3 in (B2) |
| Mid Sem Exam (03-09-18) |
Model Solution | -- | Chapter 2 in (B8); Chapter 3 in (B2) |
| Lecture 15 (11-09-18) |
Joint PMFs of multiple random variable; Conditioning a random variable on an event and another random variable |
-- | Chapter 2 in (B8) |
| Lecture 16 (12-09-18) |
Conditional expectation: definition; total expectation theorem; linearity of conditional expectation applications of conditional expectation -- expectation and variance of geometric random variable, branching process |
-- | Chapter 2 in (B8); Chapter 2 in (B2) |
| Lecture 17 (13-09-18) |
Conditional independence -- independence of a random variable from an event, independence of random variables; mean and variance of sample mean; Moment generating functions |
-- | Chapter 2 in (B8); Chapter 4 in (B2) |
| Lecture 18 (17-09-18) |
Chernoff bounds | -- | Chapter 4 in (B2) |
| Lecture 19 (18-09-18) |
Chernoff bounds and parameter estimation; continuous random variable, PDF, CDF | -- | Chapter 4 in (B2), Chapter 3 in (B8) |
| Lecture 20 (20-09-18) |
Continuous random variable, PDF, CDF | -- | Chapter 3 in (B8) |
| Lecture 21 (03-10-18) |
Continuous random variable, PDF, CDF | -- | Chapter 3 in (B8) |
| Lecture 22 (04-10-18) |
Normal distribution | -- | Chapter 3 in (B8) |
| Lecture 23 (08-10-18) |
Normal distribution, sum of random variables and moment generating functions Probabilistic methods |
-- | Chapter 4 in (B8), (B10) |
| Lecture 24 (11-10-18) |
Probabilistic methods | -- | Chapter 35 in (B11) |
| Lecture 25 (22-10-18) |
Weak Law of Large Numbers, Central Limit Theorem | -- | Chapter 8 in (B1), Chapter 5 in (B8) |
| Lecture 26 (23-10-18) |
Central Limit Theorem, Strong Law of Large Numbers | -- | Chapter 8 in (B1), Chapter 5 in (B8) |
| Lecture 27 (30-10-18) |
Stochastic Processes; Bernoulli Process | -- | Chapter 6 in (B8) |
| Lecture 28 (01-11-18) |
Discrete Time Markov Chain; Random walks in graphs | -- | Chapter 7 in (B2), Chapter 7 in (B8) |
| Problems | POSTED ON | SOLUTIONS |
| Problem Sheet 1 | August 25, 2018 | -- |
| Problem Sheet 2 | September 20, 2018 | -- |
| Problem Sheet 3 | October 9, 2018 | -- |
| Problem Sheet 4 | October 25, 2018 | -- |
| Class Tests | Date, Time and Venue | SOLUTIONS |
| Class Test 1 | August 27, 2018; 6 pm, Room 716-717 | Solutions |
| Class Test 2 | September 27, 2018; 10 am, Room 716-717 | Solutions |
| Class Test 3 (Syllabus is Lecture 21 onwards; it includes continuous random variables) |
November 8, 2018; 10:30 am, Room 716-717 | Solutions |