# Discrete Mathematics I

IIT Roorkee Course , Prof. Sugata Gangopadhyay

423 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 11: Mathematical Induction(1)

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
4.5 (2 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

# 4.5

2 Rates
5
50%
1
4
50%
1

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