Discrete Mathematics I

Overview

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;Logic:Proposition, predicate logic, logic operators, logic proposition and proof, method of proofs - Mathematical Induction Different forms of the principle of mathematical induction. selected problems on mathematical induction - Discrete Probability: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;Graph theory: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;Relations: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;Partially Ordered Sets and Lattices - Partial order relations; POSETS; lattices - 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 - Discrete Numeric Functions:Introduction of discrete numeric functions; asymptotic behaviour; generating functions;Recurrence Relations: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