## CS 201: Mathematics for Computer Science - I

##### Units: 3-0-0-9

##### Pre-requisites: None

### Course Contents:

- Mathematical proofs, proofs by induction, by contradiction, proving the contrapositive.
- Basic counting techniques, pigeon-hole principle, recurrence relations, generating functions, principle of inclusion and exclusion, Mobius inversion.
- Graphs, trees - definitions. Connectivity, paths, cycles, Eulerian walks, Hamiltonian cycles, cliques, colourings, graph matching, planarity.
- Discrete probability. Sample space, events, probability - basic laws, discrete random variable, expectation, linearity of expectation, independence, conditioning, Bayes theorem, Bernoulli, binomial and geometric distributions, moments and deviations, Markov, Tchebyshevâ€™s inequalities, Chernoff bounds.
- Application of probabilistic methods in combinatorics and graph theory.

### Books and References:

- Peter Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1995.
- JH van Lint, RM Wilson, A Course in Combinatorics, 2nd Ed., Cambridge University Press, 2001.
- David Stirzaker, Elementary Probability, 2nd Ed., Cambridge University Press, 2003.
- Noga Alon, Joel Spencer, The Probabilistic Method, 3rd Ed., Wiley Interscience, 2008.
- R Graham, D Knuth, O Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd Ed., Addison-Wesley, 1994.