Discrete Mathematics I

IIT Roorkee Course , Prof. Sugata Gangopadhyay

419 students enrolled

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

Lecture 21: Shortest path problem

Up Next
You can skip ad in
SKIP AD >
Advertisement
      • 2x
      • 1.5x
      • 1x
      • 0.5x
      • 0.25x
        EMBED LINK
        COPY
        DIRECT LINK
        PRIVATE CONTENT
        OK
        Enter password to view
        Please enter valid password!
        0:00
        0 (0 Ratings)

        Lecture Details

        Discrete Mathematics by Dr. Sugata Gangopadhyay & Dr. Aditi Gangopadhyay,Department of Mathematics,IIT Roorkee.For more details on NPTEL visit httpnptel.ac.in

        LECTURES



        Review


        0

        0 Rates
        1
        0%
        0
        2
        0%
        0
        3
        0%
        0
        4
        0%
        0
        5
        0%
        0

        Comments Added Successfully!
        Please Enter Comments
        Please Enter CAPTCHA
        Invalid CAPTCHA
        Please Login and Submit Your Comment