Metadata
Title
CSE
Category
undergraduate
UUID
86066c495ba64611832444b3a777e801
Source URL
https://cse.iitk.ac.in/pages/CS203.html
Parent URL
https://cse.iitk.ac.in/pages/Courses.html
Crawl Time
2026-03-18T08:20:49+00:00
Rendered Raw Markdown

CSE

Source: https://cse.iitk.ac.in/pages/CS203.html Parent: https://cse.iitk.ac.in/pages/Courses.html

CS 203: Mathematics for Computer Science - III

Units: 3-0-0-9 (modular first half)
Pre-requisites: None
Basics of Probability Theory : [Weeks 1]

Sets, The concept of a discrete sample space in probability theory. The definition of an event. The definition of a probability distribution. De Morgan’s Law, Union Bounds

Distributions : [Weeks 2]

Random variables, expectation, and variance.

Discrete distributions: Bernoulli trials, Geometric, Binomial and Hypergeometric and Negative Binomial distributions, Poisson distribution.  Continuous distributions: normal and other continuous distributions. Exercises based on the analysis of applications to computer science.

Linearity of expectation. Higher moments of a random variable, moment generating function. Computing the moments of geometric, binomial, normal, and Poisson distributions.

OPTIONAL (if time permits): Function of One Random Variable: Change of Variables.

Conditional Probability : [Weeks 3]

Conditional Probability, Conditional expectation of a random variable with respect to an event. Bayes' Theorem and examples of applications in computer science.

Independence: [Weeks 4]

The concept of k-wise and mutual independence of random variables. Applications of independence and k-wise independence in computer science.

Tail Bounds: [Week 5]

Tail bounds: Markov inequality, Chebyshev's Inequality, Chernoff bound, and Examples of applications to the analysis of randomized algorithms.

Applications: [Week 6 & 7]

Cover one or more applications: For example,

  1. Statistics: Hypothesis Testing
  2. Parameter Estimation: MLE, Least Squares
  3. Introduction to the probabilistic method. Applications to random graphs and number theory. Lovasz Local Lemma and applications
  4. Information theory
  5. Markov chains
  6. Randomized algorithms/ Streaming
Books / References:
  1. William Feller, An introduction to probability theory and its applications.
  2. Sheldon Ross, A first course in probability.
  3. David Stirzaker, Elementary probability.
  4. Kai Lai Chung, A course in probability theory.
  5. Athanasios Papoulis and S Pillai, Probability - Random Variables and Stochastic Processes, Chapter 5, for Change of Variable concept