| Course Outline | General Information | Study Material | Lectures (classwise) | Assignments and exams (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: | Wednesday 09:30-11:15, Friday 09:30-11:15 Room No. 718, S. N. Bose Bhavan (Library Building) |
| 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 |
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 0 (10-07-13) |
Introduction, uses of probability in CS | -- | -- |
| Lecture 1 (12-07-13) |
Introduction to probability, sample space and events; axioms of probabilty and some propositions |
-- | (B1) |
| Lecture 2 (17-07-13) |
Counting in a nutshell -- I counting (using) functions, principle of inclusion and exclusion: derangement |
-- | (B6), (B7) |
| Lecture 3 (19-07-13) |
Counting in a nutshell -- II (un)ordered sampling with(out) replacement Occupancy problems: (in)distinguishable balls into (in)distinguishable bins |
-- | (B6), (B7) |
| Lecture 4 (24-07-13) |
Problems and exercises in probability | -- | (B1) |
| Lecture 5 (26-07-13) |
Problems and exercises in probability | -- | (B1), (B3) |
| Lecture 6 (31-07-13) |
Conditional probability and independence | -- | (B1) |
| Lecture 7 (02-08-13) |
Conditional probability and independence | -- | (B1), (B3) |
| Lecture 8 (07-08-13) |
Conditional probability and independence | -- | (B1), (B3) |
| Lecture 9 (14-08-13) |
Discrete random variables and expectation | -- | (B1), (B2), (B3) |
| Lecture 10 (16-08-13) |
Discrete random variables: expectation and variance | -- | (B1), (B2), (B3) |
| Lecture 11 (20-08-13) |
Bernoulli trials, Geometric random variable and Binomial random variable. Markov's and Chebyshev's inequality |
-- | (B1), (B2), (B3) |
| Lecture 12 (21-08-13) |
Continuous random variables | -- | (B1), (B3) |
| Lecture 13 (23-08-13) |
Continuous random variables and continuous distributions | -- | (B1), (B3) |
| Lecture 14 (11-09-13) |
Balls and bins, Poisson distribution | -- | (B1), (B2) |
| Lecture 15 (13-09-13) |
Negative binomial and hypergeometric distribution | -- | (B1), (B3) |
| Lecture 16 (18-09-13) |
Joint distribution and independent random variables | -- | (B1), (B3) |
| Lecture 17 (20-09-13) |
Sums of independent random variables Conditional distributions, Change of variables in joint distributions |
-- | (B1), (B3) |
| Lecture 18 (25-09-13) |
Properties of expectation -- Coupon collection, random ordering and applications to hashing, randomized quicksort |
-- | (B1), (B3) |
| Lecture 19 (27-09-13) |
Moment generating functions, Chernoff bounds |
-- | (B1), (B3) |
| Lecture 20 (30-09-13) |
Covariance, variance of sums and correlations | -- | (B1), (B3) |
| Lecture 21 (04-10-13) |
Conditional expectation | -- | (B1), (B3) |
| Lecture 22 (07-10-13) |
Conditional expectation, branching process |
-- | (B1), (B3) |
| Lecture 23 (09-10-13) |
Computing probabilities by conditioning, secretary hiring problem Conditional variance |
-- | (B1), (B3) |
| Lecture 24 (21-10-13) |
Probabilistic methods | -- | (B2) |
| Lecture 25 (23-10-13) |
Weak law of large numbers, Central limit theorem, Strong law of large numbers |
-- | (B1) |
| Lecture 26 (25-10-13) |
Simulations | -- | (B1) |
| Lecture 27 (28-10-13) |
Simulations | -- | (B1) |
| Lecture 28 (30-10-13) |
Markov chains | -- | (B2), (B1), (B3) |
| Lecture 29 (01-11-13) |
Markov chains | -- | (B2), (B1), (B3) |
| ASSIGNMENTS | POSTED ON | SUBMISSION DEADLINE | SOLUTIONS |
| Set I (prepared by Sameer Desai) |
July 30, 2013 | August 7, 2013 (after class) Submit to Sameer Desai |
Solution sketch and answers
(prepared by Sameer Desai) |
| Set II (prepared by Sameer Desai) |
August 22, 2013 | September 13, 2013 (after class) Submit to Sameer Desai |
-- |
| Mid Semestral exam | September 6, 2013 | -- | Model solution |
| Set III (prepared by Sameer Desai) |
November 6, 2013 | November 29, 2013 Submit to Sameer Desai |
-- | Set IV (prepared by Sameer Desai) |
November 6, 2013 | November 29, 2013 Submit to Sameer Desai |
-- |