1) Set Theory
Introduction to the theory of sets; combination of sets; power sets; finite and infinite sets; principle of inclusion and exclusion; selected problems from each topic.
Proposition, predicate logic, logic operators, logic proposition and proof, method of proofs.
Different forms of the principle of mathematical induction. selected problems on mathematical induction.
Counting principles. Random experiment; sample space; events; axioms of probability; conditional probability. Theorem of total probability; Bayes' theorem. Application to information theory: information and mutual information.
Path, cycles, handshaking theorem, bipartite graphs, sub-graphs, graph isomorphism, operations on graphs, Eulerian graphs and Hamiltonian graphs, planar graphs, Euler formula, traveling salesman problem, shortest path algorithms.
Definitions and properties; Equivalence relations and equivalence classes. Representations of relations by binary matrices and digraphs; operations on relations. Closure of a relations; reflexive, symmetric and transitive closures. Warshall's algorithm to compute transitive closure of a relation.
7)Partially Ordered Sets and Lattices
Partial order relations; POSETS; lattices
8)Boolean Algebra and Boolean Functions Introduction to Boolean algebra and Boolean functions. Different representations of Boolean functions. Application of Boolean functions to synthesis of circuits
9)Discrete Numeric Functions
Introduction of discrete numeric functions; asymptotic behaviour; generating functions.
Linear recurrence relations with constant coefficients (homogeneous case); discussion of all the three sub-cases. Linear recurrence relations with constant coefficients (non-homogeneous case); discussion of several special cases to obtain particular solutions. Solution of linear recurrence relations using generating functions.