1.1 Introduction and significance of discrete mathematics
1.2 Sets Cantorian set theory axiomatic set theory set operations cardinality of sets principal of inclusion and exclusion
1.3 Types of sets Bounded and unbounded sets diagonalization argument countable and uncountable sets finite and infinite sets countably infinite and uncountably infinite sets power set
1.4 Propositional logic logic propositional equivalences application of propositional logic translating English sentences
1.5 Proof by mathematical induction and strong mathematical induction
Unit - 2 Relations and Functions
2.1 Relations and their properties
2.2 Nary relations and their applications
2.3 Representing relations Closures of relations
2.4 Partial orderings partitions Hasse diagram
2.5 Lattices chain and antichain
2.6 Transitive closure and Warshall’s algorithm
2.7 Functions Surjective injective bijective functions identity functions partial functions invertible function constant function inverse functions and composition of functions
2.8 The Pigeonhole principle.
Unit - 3 Counting Principle
3.1 The basics of counting Rule of sum and product
3.2 Permutations and combinations
3.3 Binomial coefficients and identities
3.4 Generalized permutations and combinations
3.5 Algorithms for generating permutations and combinations.
Unit - 4 Graph-Theory
4.1 Graph terminology and special types of graphs.
4.2 Representing graphs and Graph isomorphism connectivity.
4.3 Euler and Hamiltonpaths The Handshaking Lemma.
4.4 Single source shortest pathDijkstra’s Algorithm.
4.5 Planar Graphs Graph Coloring.
Unit - 5 TREES
5.1 Introduction
5.2 Properties of trees
5.3 Binary search tree
5.4 Tree traversal
5.5 Decision tree
5.6 Prefix codes and Huffman coding cut sets.
5.7 Spanning trees and Minimum spanning tree
5.8 Kruskal’s and Prim’s algorithms
5.9 The maxflowmin cut theorem Transport network
Unit - 6 Algebraic Structures and Coding Theory
6.1 The structure of algebra.
6.2 Algebraic systems.
6.3 Semigroups Monoids Groups.
6.4 Homomorphism Normal subgroups and Congruence relations.
6.5 Rings Integral Domains and Fields.
6.6 Coding theory Polynomial rings and Polynomial codes.