#### CS 202/3: Mathematics for Computer Science - II/III

###### Course: CS202

###### Units: 3-0-0-9 (modular second half)

###### Pre-requisites: None

###### Course Contents:

- Propositional logic syntax and semantics.
- Tautologies, axiom system and deduction.
- Proof of soundness and completeness.
- First order logic syntax and semantics.
- Structures, models, satisfaction and validity.
- Axiomatization, soundness and completeness.
- Optional: some advanced topics.

###### Books and References:

- HD Ebbinghaus, J Flum, W Thomas, Mathematical Logic, 2nd Ed., Springer Verlag, 1994.
- HB Enderton, A Mathematical Introduction to Logic, 2nd Ed., Academic Press, 2001.
- RM Smullyan, First Order Logic, Dover Press, 1995.

###### Course: CS203

###### 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. Random variables, expectation and variance.

###### Distributions : [Weeks 2 and 3]

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.

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

###### [Weeks 4]

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

###### [Week 5]

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

###### [Week 6 and 7]

Introduction to the probabilistic method. Applications to random graphs and number theory. Lovasz Local Lemma and applications.

If time permits, one of the following topics can be covered: Information theory/ Markov chains/ Randomized algorithms/ Streaming.

Books:

- William Feller, An introduction to probability theory and its applications.
- Sheldon Ross, A first course in probability.
- David Stirzaker, Elementary probability.
- Kai Lai Chung, A course in probability theory.