Basics of Counting: Arithmetic and geometric progressions; Fibonacci numbers; The pigeonhole principle; Basic definitions; Pascal’s identity; The binomial theorem; The Master theorem.
Asymptotic Analysis: Limits; Orders of Growth (Big- oh O, Omega Ω and Theta Θ).
Graph Theory: Trees; Planarity; Eulerian and Hamiltonian Cycles; Matching and Colouring.
Elementary Probability Theory: Counting in event space; Probability Tree; Probability distributions; Finite probability space, probability measure, events; Conditional probability, independence, Bayes’ theorem; Integer random variables, expectation; Law of large numbers.