| 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 11:15-13:05 (NAB 1), Friday 11:15-13:05 (705-706) |
| 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 (B13) Probability and Random Processes Geoffrey R. Grimmett and David R. Stirzaker Oxford |
| Web Resources |
(W1) Richard Weber's course on Probability for first year mathematicians at Cambridge
|
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (01-08-23) |
Introductory lecture/tutorial on basics of counting | -- | |
| Lecture 2 (04-08-23) |
Probability and its uses in CS: a randomized analysis of number of updates while finding minimum;
a randomized algorithm for selection, and sorting |
-- | Chapter 13 in (B9) |
| Lecture 3 (08-08-23) |
Introduction to probability and notion of probability as a measure and axioms; Union Bound; Principle of inclusion and exclusion: derangements, balls and bins and birthday problem |
-- | Chapter 1 in (B13) and Chapter 1 in (B8) |
| Lecture 4 (11-08-23) |
Introduction to probability and its axioms; Boole's inequality; Inclusion-Exclusion Formula; probability of derangement |
-- | Chapter 1 in (B8), Chapter 1 in (B13) |
| Lecture 5 (18-08-23) |
Conditional probability; chain multiplication rule, Total probability theorem, Bayes' theorem | -- | :Chapter 1 in (B13), Chapter 1 in (B8) |
| Lecture 6 (22-08-23) |
Applications of Conditional probability; multiplication rule; Total probability theorem: Graph minimum cut, Gambler's ruin |
-- | Chapter 1 in (B2), (B1) |
| Lecture 7 (25-08-23) |
Independence and mutual independence of a collection of events; | -- | Chapter 1 in (B8), Chapters 4 and 5 in (W1) |
| Lecture 8 (29-08-23) |
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) and (B2), Chapter 7 in (W1) |
| Lecture 9 (01-09-23) |
Expectation of functions of random variables; Probability Mass Function (PMF) and Cumulatitive Distribution Function (CDF); memoryless property of geometric random variable; Markov's inequality |
-- | Chapter 2 in (B8), Chapter 3 in (B2) |
| Lecture 10 (05-09-23) |
Chebyshev inequality; mean and variance of sample mean; PMFs of Bernoulli, Binomial, Poisson, Uniform distributions: their expectation and variance |
-- | Chapter 3 in (B2), Chapter 2 in (B8) |
| Lecture 11 (08-09-23) |
Joint PMFs of multiple random variables and conditional expectation; Total expectation theorem |
-- | Chapter 2 in (B8) and (B2) |
| Lecture 12 (12-09-23) |
Applications of conditional expectation: Expectation and variance of geometric random variable; and branching process |
-- | Chapter 2 in (B2) and Chapter 2 in (B8) |
| Lecture 13 (15-09-23) |
Independence of random variable; Sum of independent Poisson random variables; Covariance, correlation coefficient; conditional expectation as an estimator Conditional variance and law of total variance |
-- | Chapter 2 and 4 in (B8) |
| Mid Sem Exam (21-09-23) |
Model Soultion for mid sem exam (Solution for those problems not done in class.) |
-- | -- |
| Lecture 14 (26-09-23) |
Moment generating functions; Chernoff bounds |
-- | Chapter 4 in (B2) |
| Lecture 15 (29-09-23) |
Applications of Chernoff bound: load balancing, sample size estimation | -- | Chapter 4 in (B2) and Chapter 13 in (B9) |
| Lecture 16 (03-10-23) |
Probabilistic methods | -- | Chapter 6 in (B2) |
| Lecture 17 (06-10-23) |
Continuous random variable, PDF, CDF | -- | Chapter 3 in (B8) |
| Lecture 18 (10-10-23) |
Continuous random variable, PDF and CDF | -- | Chapter 3 in (B8) |
| Lecture 19 (13-10-23) |
Normal, standard normal random variables: expectation, variance and use of standard normal tables | -- | Chapter 3 in (B8) |
| Lecture 20 (17-10-23) |
Transforms (MGF) associated with random variables | -- | Chapter 4 in (B8) |
| Lecture 21 (31-10-23) |
Weak Law of Large Numbers. Strong Law of large Numbers | -- | Chapter 5 in (B8) |
| Lecture 22 (03-11-23) |
Central Limit Theorem | -- | Chapter 5 in (B8), Chapter 8 in (B1) |
| Lecture 23 (04-11-23) |
Introduction to Stochastic Processes: Bernoulli processes Introduction to Martingales |
-- | Chapter 6 in (B8) (B2) |
| Lecture 24 (14-11-19) |
Introduction to Martingales, Applications to CS: quicksort, hashing, crossing lemma |
-- | Chapter 13 in (B2), Chapter 2 and 5 in (B2), (B11) |
| Lecture 25 (16-11-19) |
Introduction to Markov Chains and Random Walks | -- | Chapter 7 in (B2) |
| Problems | POSTED ON | SOLUTIONS |
| Tutorial Sheet 1 | August 28, 2023 | Solution discussed by Uddalok and Debarshi |
| Tutorial Sheet 2 | September 15, 2023 | Discussed by Uddalok and Debarshi |
| Tutorial Sheet 3 | -- | Discussed by Uddalok and Debarshi |
| Tutorial Sheet 4 | -- | Discussed by Uddalok and Debarshi |
| Class Tests | Date, Time and Venue | SOLUTIONS |
| Class Test I | September 8, 2023; 6:30 pm, Room 716-717 | Solutions |
| Mid Sem | September 21, 2023 | Solutions |
| Class Test II (Syllabus was informed through e-mail) | October 18, 2023; 6:30 pm onwards; Room 716-717 | Solutions |
| Class Test III | November 10, 2023; Room 716-717 | Solutions |
| ASSIGNMENTS | POSTED ON | SUBMISSION DEADLINE | SOLUTIONS |
| Problem Set |
Nov 07, 2023 | Dec 15, 2023 Submit to Debarshi Chanda and Uddalok Sarkar |
-- |