Sets, Mathematical Induction and Inclusion-Exclusion Principle

• Introduction
• Set
• Notation
• Representation of set
• Standard set
• Symbols in set
• Finite and infinite set
• Order of set / cardinality
• Type of sets
• Subsets and proper subsets
• Power set
• Sets of set
• Universal set
• Venn- Euler diagram
• Union of sets
• Intersection of sets
• Disjoint sets
• Difference of sets
• Symmetric difference of two sets
• Complementary set or complement of set
• Algebraic laws of sets
• Cartesian product of two sets
• de-Morgan’s Law
• Deduction and induction
• Principle of mathematical induction
• Principle of inclusion and exclusion
• The generalized inclusion-exclusion principle

Language and Grammar

• Introduction
• Ordered set
• Alphabets

Word
Empty word
String
Sub-words and initial segments

• Set of words
• Language
• Operations on languages
• Regular expression
• Regular language
• Grammar or phase-structured grammar
• Types of grammar

Permutation and Combination

• Introduction
• Factorials
• Permutation

Permutation with repetitions
Circular or cyclic permutation

• Combinations
• Important results of combinations

Relation and Function

• Introduction
• Relation
• Domain and range of a relation
• Inverse relation
• Complement of a relation
• Representation of relation
• Types of relation
• Equivalence class

Properties of equivalence classes
Quotient set

• Partition of set
• Closures and their types

Reflexive closure
Symmetric closure
Transitive closure

• Partial order relation, POR
• Total order relation, TOR
• Partially ordered set
• Total ordered relation
• Dual of the partial order relation
• Hasse diagram
• Lower and upper bounds

Greatest lower bound, glb
Least upper bound, lub

• Lattice

Sublattice
Bounded lattices
Distributive lattices
Complement of an element of lattice
Complemented lattice
Chain

• Functions
• Some standard functions
• Types of functions

One-one function
Onto function or Surjective function
One-one onto or Bijective function
Many-one function
Inverse function

• Composition of function or composite function
• Pigeonhole principle

Generalized pigeonhole principle

Graph Theory

• Introduction
• Graph
• Basic terminology
• Types of graph

Finite and infinite graph
Simple graph
Multi graph
Pseudo graph
Null graph
Drawing of graph

• Some special type of simple graphs
• Regular graph
• Complete graph
• Bipartite graph
• Complete bipartite graph
• Complementary graph
• Cycle
• Wheel
• Subgraph
• Operations on graph

Union of two graphs
Intersection of two graphs
Ring sum of two graphs
Join of two graphs
Product of two graphs

• Isomorphism of graphs
• Connectedness
• Walk
• Important definition related to walk
• Weighted graphs
• Shortest path problem
• Euler or Eulerian graphs
• Euler theorem
• Hamiltonian cycle and path
• Hamiltonian graph
• Travelling salesman problem
• Planar graph
• Region of graph
• Euler formula
• Directed graph or digraphs

Different vertex in a digraph
Types of directed graph
Isomorphism in digraphs

• Digraphs and binary relations
• Matrix representation of graphs

Adjacency matrix
Incidence matrix
Relation between adjacency matrix and incidence matrix

• Adjacency and incidence matrix of digraph

Tree

• Introduction
• Tree
• Elementary theorems and important properties of trees
• Some important definitions

Distance between two vertices
Eccentricity of a vertex
Centre of graph
Radius and diameter of a tree

• Forest
• Rooted tree
• Subtree
• Ordered rooted tree
• Binary tree
• Properties of binary tree
• Height and path length of a binary tree
• Balanced rooted tree
• Labelled tree and binary decision tree
• Spanning tree
• Minimal spanning tree
• Methods of finding minimal spanning tree

Kruskal’s algorithm
Prim’s algorithm

Finite State Machine

• Introduction
• Information processing machine
• Finite state machine
• Representation of finite state machine
• Equivalent machines
• Equivalent states
• Finite state machine as language recognizers
• Finite state language
• Finite state automata)
• Pumping lemma

Recurrence Relation and Recursive Algorithms

• Discrete numeric function
• Operations on numeric functions
• Generating function
• Generating functions of some simple numeric functions
• Generating functions of some specific numeric functions
• Recurrence relation

Linear recurrence relations with constant coefficients
Homogeneous linear recurrence relations with constant coefficients

• Recursive algorithms or solution of a linear recurrence relation

Homogeneous solution
Particular solution
Total solution

• Solution by the method of generating function

Boolean Algebras-Lattice

• Introduction
• Partial order relation, POR
• Total order relation, TOR
• Lower and upper bounds

Greatest lower bound, glb
Least upper bound, lub

• Lattice
• Sublattice
• Boolean algebra
• Duality
• Principle of duality
• Properties of Boolean algebra
• Order relation or inclusion relation in a Boolean algebra
• Boolean expression and their equivalence
• Boolean functions
• Maxterm and Minterm
• Normal form of Boolean functions

Conjunctive normal form or CNF
Disjunctive normal form or DNF

• Complementary function of a Boolean function
• Boole’s expansion theorem

Logic and Propositional Calculus

• Introduction
• Sentence and proposition
• Types of statement
• Logical connectives
• Some special definitions
• Basic logical operations and their truth tables

Conjunction, ∧
Disjunction, ∨
Negation, ~
Tautology
Fallacy or contradiction
Implication or conditional statement
Converse, inverse and contraposition of an implication or conditional statement
Biconditional
Logical equivalence
Exclusive OR, ⊕

• Algebra of propositions
• Algebraic structure
• Logic and bit operations
• Logical connectives NAND and NOR
• Validity of argument

Switching Circuit

• Introduction
• Switch
• Combination of switches: Switch in series and Switch in parallel
• Mixed combination of switches
• Applications of two or more switches
• Circuit with composite operations
• Logic circuit elements
• Basic logic gates
• Universal gate : NAND and NOR gate
• XOR and XNOR gate

Brief Review of Group and Ring

• Introduction
• Cartesian product
• Algebraic structure
• Binary operation
• Group
• Finite and infinite group
• Groupoid or quasi group
• Semi-group
• Monoid
• Commutative or abelian group
• Order of a group
• Modulo operation
• Uniqueness property in group
• Integral power of an element of group
• Order of an element of a group
• Subgroup
• Examples of subgroup
• Coset
• Lagrange’s theorem
• Cyclic group
• Homomorphism
• Types of homomorphism
• Kernel of homomorphism
• Ring
• Examples of ring
• Commutative ring
• Ring with unity
• Ring with zero divisor
• Ring without zero divisor
• Integral domain
• Division ring
• Field
• Boolean ring
• Cancellation laws in ring
• Unit element of a ring
• Characteristic of a ring
• Characteristic of an integral domain and field
• Subring)
• Improper or trivial subring
• Examples of subring
• Necessary and sufficient condition for a subring
• Intersection of two subrings
• Subfield
• Prime field
• Examples of Subfield