CS 201: Mathematics for Computer Science - I

Units: 3-0-0-9
Pre-requisites: None

Course Contents:

  1. Mathematical proofs, proofs by induction, by contradiction, proving the contrapositive.
  2. Basic counting techniques, pigeon-hole principle, recurrence relations, generating functions, principle of inclusion and exclusion, Mobius inversion.
  3. Graphs, trees - definitions. Connectivity, paths, cycles, Eulerian walks, Hamiltonian cycles, cliques, colourings, graph matching, planarity.
  4. 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.
  5. Application of probabilistic methods in combinatorics and graph theory.

Books and References:

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