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

Course: CS202

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

Pre-requisites: None

Course Contents:

1. Propositional logic syntax and semantics.
2. Tautologies, axiom system and deduction.
3. Proof of soundness and completeness.
4. First order logic syntax and semantics.
5. Structures, models, satisfaction and validity.
6. Axiomatization, soundness and completeness.
7. Optional: some advanced topics.

Books and References:

1. HD Ebbinghaus, J Flum, W Thomas, Mathematical Logic, 2nd Ed., Springer Verlag, 1994.
2. HB Enderton, A Mathematical Introduction to Logic, 2nd Ed., Academic Press, 2001.
3. 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:

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.