This course covers several important topics of Discrete Mathematics. This includes Set thoery and logic, relations, partially ordered sets, Boolean algebra and Boolean functions,analysis of algorithms, recurrence relations, finite state machines, discrete probability and graph theory. The applications of these topics are also discussed.

Lectures

Topic

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.

2-10

Logic
Proposition, predicate logic, logic operators, logic proposition and proof, method of proofs.

11-12

Mathematical Induction
Different forms of the principle of mathematical induction. selected problems on mathematical induction.

13-17

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.

18-23

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.

24-29

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.

30-32

Partially Ordered Sets and Lattices
Partial order relations; POSETS; lattices

33-35

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

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.

Mathematics of Higher Secondary level

Liu C. L. , Elements of Discrete Mathematics, Second Edition, Mc Graw Hill 1985.

Mott J. L. , Kandel A. and Baker T. P., Discrete Mathematics for Computer
Scientists and Mathematicians, Second Edition, Prentice Hall India, 1986.

Harary F., Graph Theory, Narosa, 1969.

Thomas H. C.,Ã‚Â Leiserson C. E.; Rivest R. L.; Stein C.,Ã‚Â Introduction toÃ‚Â
AlgorithmsÃ‚Â (2nd ed.). MIT Press and McGraw-Hill. 2001.

Thomas Koshy: Discrete Mathematics with Applications, Academic Press, 2004

Important: Please enable javascript in your browser and download Adobe Flash player to view this site
Site Maintained by Web Studio, IIT Madras. Contact Webmaster: nptel@iitm.ac.in