Courses with significant overlap with this course:

Semester of last offering:

Date of approval: dd-mmm-yyyy

Prerequisites:  

Course Contents

1. Mathematical proofs, proofs by induction, by contradiction, proving the contra positive.

2. Basic counting techniques, pigeonhole principle, recurrence relations, generating functions, principle of inclusion and exclusion, Mobius inversion.

3. Graphs, trees definitions. Connectivity, paths, cycles, Euler Ian walks, Hamiltonian cycles, cliques, colorings, graph matching, planarity.

4. Discrete probability. Sample space, events, probability basic laws, discrete random variable, expectation, linearity of expectation, independence, conditioning, Bays theorem, Bernoulli, binomial and geometric distributions, moments and deviations, Markov, Tchebyshev 's inequalities, Chern off bounds.

5. Application of probabilistic methods in combinatory and graph theory.

Topics