Course Objectives

This course introduces most of the core mathematical ideas and tools for computer science. These include a) mathematical proofs, set theory and relations b) combinatorics c) basic graph theory d) discrete probability and simple applications in combinatorics and graph theory.

Topics and reference material

Topics

The course has 4 broad units (not of equal length):
  1. Mathematical proofs, proofs by induction, by contradiction, proving the contrapositive. Finite and infinte sets.
  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. Application of probabilistic methods in combinatorics and graph theory.
Reference material

We will put up notes/summaries for each topic that we discuss and pointers to sources. Typically these will be internet resources. There are many good video lectures on these topics on youtube or other university sites. Pl. do look at them.

The main resource is the OCW MIT course on Math for CS (2015 edition). But we will deviate from this at several points. Pl. see the course ftp site for a copy of the OCW book and other reference material.

A very important component is solving problems. To really understand the material you have to try and solve lots of them.

The books below are useful references. They contain much more material than we will have time for in the course.

  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.