| 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 14:00-16:00 (ACMU Seminar room), Thursday 14:00-16:00 (ACMU seminar room) |
| 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 (23-07-24) |
Introductory lecture | -- | |
| Lecture 2 (26-07-24) |
Problems in counting | -- | |
| Lecture 3 (30-07-24) |
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 (02-08-24) |
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 (06-08-24) |
Problem solving | -- | |
| Lecture 6 (09-08-24) |
Conditional probability; chain multiplication rule, Total probability theorem, Bayes' theorem | -- | Chapter 1 in (B13), Chapter 1 in (B8) |
| Lecture 7 (13-08-24) |
Applications of Conditional probability; multiplication rule; Total probability theorem: Graph minimum cut, Gambler's ruin | -- | Chapter 1 in (B2), (B1) |
| Lecture 8 (20-08-24) |
Applications of Conditional probability: Gambler's ruin Independence and mutual independence of a collection of events; |
-- | Chapter 1 in (B8), Chapters 4 and 5 in (W1) |
| Lecture 9 (22-08-24) |
Independence and mutual independence of a collection of events; Bernoulli trial; Simulating an unbiased coin from a biased coin; Problem of points; Laplace's rule of succession |
-- | Chapter 1 in (B8), Chapters 5 and 6 in (W1) |
| Lecture 10 (23-08-24) |
Discrete random variable and their expectation; Linearity of expectation; Functions of random variables; Jensen's inequality |
-- | Chapter 2 in (B8) and Chapter 3 in (B2) |
| Lecture 11 (27-08-24) |
Some distributions and their pmf and properties, Applications: Guessing games with and without memory; Coupon collector; Quicksort |
-- | Chapter 1 in (B13) and Chapter 1 in (B8) |
| Lecture 12 (29-08-24) |
Memoryless property of geometric random variable; expectation Variance and moments of a random variable; covariance and independence; Mean and variance of sample mean; Markov's and Chebyshev's inequality |
-- | Chapter 2 in (B8), Chapter 3 in (B2) |
| Lecture 13 (03-09-24) |
Discrete uniform random variable, Joint PMF of multiple random variable, Conditioning a random variable on an event | -- | Chapter 2 in (B8) |
| Lecture 14 (05-09-24) |
Conditioning a random variable on another random variable, Conditional expectation, Total expectation theorem, Expectation and variance of Geometric random variable | -- | Chapter 2 in (B8), Chapter 3 in (B2) |
| Mid Sem (17-09-24) |
Model Soultion for mid sem exam | -- | |
| Lecture 15 (19-09-24) |
Conditional expectation, Branching process, Independence of random variables | -- | Chapter 2 in (B8), Chapter 3 in (B2) |
| Lecture 16 (23-09-24) |
Secretary hiring problem, Conditional expectation as an estimator | -- | Chapter 2 in (B8), Chapter 3 in (B2) |
| Lecture 17 (24-09-24) |
Probabilistic methods -- large cut, independent set | -- | Chapter 6 in (B2) |
| Lecture 18 (26-09-24) |
Probabilistic methods -- Ramsey number, number of triangles in a random graph and threshold behaviour | -- | Chapter 6 in (B2) |
| Lecture 19 (01-10-24) |
Moment Generating Functions and Chernoff Bounds; Chernoff bounds for sum of Poisson trials | -- | Chapter 4 in (B2) |
| Lecture 20 (03-10-24) |
Chernoff Bounds and its applications: load balancing, sample size estimation | -- | :Chapter 4 in (B2) |
| Lecture 21 (15-10-24) |
Continuous random variable, PDF, CDF | -- | Chapter 3 in (B8) |
| Lecture 22 (17-10-24) |
Continuous random variable, PDF and CDF | -- | Chapter 3 in (B8) |
| Lecture 23 (22-10-24) |
Transforms and moments; Normal random variable | -- | Chapter 4 in (B8) |
| Lecture 24 (24-10-24) |
Weak Law of Large Numbers; Central Limit Theorem | -- | Chapter 5 in (B8) |
| Lecture 25 (29-10-24) |
Strong Law of Large Numbers | -- | Chapter 5 in (B8) |
| Lecture 26 (04-11-24) |
Martingales | -- | Chapter 12 in (B2) |
| Lecture 27 (05-11-24) |
Markov Chain and Random Walk | -- | Chapter 7 in (B2) |
| Lecture 28 (07-11-24) |
Markov Chain and Random Walk | -- | Chapter 7 in (B2) |
| Problems | POSTED ON | SOLUTIONS |
| Tutorial Sheet 1 | August 23, 2024 | -- |
| Class Tests | Date, Time and Venue | SOLUTIONS |
| Class Test I | September 2, 2024; 6:00 pm, Room 716-717 | Solutions |
| Class Test II | September 21, 2024; 6:30 pm onwards; Room 716-717 | Solutions |
| Class Test III | November 11, 2024; Room 716-717 | Solutions |
| ASSIGNMENTS | POSTED ON | SUBMISSION DEADLINE | SOLUTIONS |