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):
- Mathematical proofs, proofs by induction, by contradiction, proving the
contrapositive. Finite and infinte sets.
- 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.
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.
- 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.