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:1513:05 (NAB 1), Friday 11:1513:05 (705706) 
The necessary evil  marks, exam, etc.:  Midsem: 25, Endsem: 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 (010823) 
Introductory lecture/tutorial on basics of counting    
Lecture 2 (040823) 
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 (080823) 
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 (110823) 
Introduction to probability and its axioms; Boole's inequality; InclusionExclusion Formula; probability of derangement 
  Chapter 1 in (B8), Chapter 1 in (B13) 
Lecture 5 (180823) 
Conditional probability; chain multiplication rule, Total probability theorem, Bayes' theorem    Chapter 1 in (B13), Chapter 1 in (B8) 
Lecture 6 (220823) 
Applications of Conditional probability; multiplication rule; Total probability theorem: Graph minimum cut, Gambler's ruin 
  Chapter 1 in (B2), (B1) 
Lecture 7 (250823) 
Independence and mutual independence of a collection of events;    Chapter 1 in (B8), Chapters 4 and 5 in (W1) 
Lecture 8 (290823) 
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 (010923) 
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 (050923) 
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 (080923) 
Joint PMFs of multiple random variables and conditional expectation; Total expectation theorem 
  Chapter 2 in (B8) and (B2) 
Lecture 12 (120923) 
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 (150923) 
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 (210923) 
Model Soultion for mid sem exam (Solution for those problems not done in class.) 
   
Lecture 14 (260923) 
Moment generating functions; Chernoff bounds 
  Chapter 4 in (B2) 
Lecture 15 (290923) 
Applications of Chernoff bound: load balancing, sample size estimation    Chapter 4 in (B2) and Chapter 13 in (B9) 
Lecture 16 (031023) 
Probabilistic methods    Chapter 6 in (B2) 
Lecture 17 (061023) 
Continuous random variable, PDF, CDF    Chapter 3 in (B8) 
Lecture 18 (101023) 
Continuous random variable, PDF and CDF    Chapter 3 in (B8) 
Lecture 19 (131023) 
Normal, standard normal random variables: expectation, variance and use of standard normal tables    Chapter 3 in (B8) 
Lecture 20 (171023) 
Transforms (MGF) associated with random variables    Chapter 4 in (B8) 
Lecture 21 (311023) 
Weak Law of Large Numbers. Strong Law of large Numbers    Chapter 5 in (B8) 
Lecture 22 (031123) 
Central Limit Theorem    Chapter 5 in (B8), Chapter 8 in (B1) 
Lecture 23 (041123) 
Introduction to Stochastic Processes: Bernoulli processes Introduction to Martingales 
  Chapter 6 in (B8) (B2) 
Lecture 24 (141119) 
Introduction to Martingales, Applications to CS: quicksort, hashing, crossing lemma 
  Chapter 13 in (B2), Chapter 2 and 5 in (B2), (B11) 
Lecture 25 (161119) 
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 716717  Solutions 
Mid Sem  September 21, 2023  Solutions 
Class Test II (Syllabus was informed through email)  October 18, 2023; 6:30 pm onwards; Room 716717  Solutions 
Class Test III  November 10, 2023; Room 716717  Solutions 
ASSIGNMENTS  POSTED ON  SUBMISSION DEADLINE  SOLUTIONS 
Problem Set 
Nov 07, 2023  Dec 15, 2023 Submit to Debarshi Chanda and Uddalok Sarkar 
 