The course aims to introduce the students to Boolean algebra, sets, relations, functions, principles of counting, and growth functions so that these concepts may be used effectively in other courses.
At the end of the course, students should be able to:
Introduction: Sets – finite and infinite sets, uncountable infinite sets; functions, relations, properties of binary relations, closure, partial ordering relations; counting – Pigeonhole Principle, permutation and combination; mathematical induction, Principle of Inclusion and Exclusion.
Growth of Functions: asymptotic notations, summation formulas and properties, bounding summations, approximation by integrals.
Recurrence: recurrence relations, generating functions, linear recurrence relations with constant coefficients and their solution, recursion trees, Master Theorem.
Graph Theory: basic terminology, models and types, multi-graphs and weighted graphs, graph representation, graph isomorphism, connectivity, Euler and Hamiltonian Paths and Circuits, planar graphs, graph coloring, Trees, basic terminology and properties of Trees, introduction to spanning trees.
Propositional Logic: logical connectives, well-formed formulas, tautologies, equivalences, Inference Theory.