DITRP

CERTIFICATE IN DISCRETE MATHEMATICS -(C1164)

Set Theory:

Definition of Sets, Venn Diagrams, complements, cartesian products, power sets, countingprinciple, cardinality and countability (Countable and Uncountable sets), proofs of some general identitites on sets, pigeonhole principle.
Relation:Definition, types of relation, composition of relations, domain and range of a relation, pictorial representation of relation, properties of relation, partial ordering relation.
Function: Definition and types of function, composition of functions, recursively defined functions.

Propositional logic:

Proposition logic, basic logic, logical connectives, truth tables, tautologies, contradiction , normal forms(conjunctive and disjunctive), modus ponens and modus tollens, validity, predicate logic, universal and existential quantification. Notion of proof: proof by implication, converse, inverse, contrapositive, negation, and contradiction, direct proof, proof by using truth table, proof by counter example.
Combinatories:Mathematical induction, recursive mathematical definitions, basics of counting, permutations, combinations, inclusion-exclusion, recurrence relations (nth order recurrence relation with constant coefficients, Homogeneous recurrence relations, Inhomogeneous recurrence relation),generating function (closed form expression, properties of G.F., solution of recurrence relation usingG.F, solution of combinatorial problem using G.F.)

Algebraic Structure:

Binary composition and its properties definition of algebraic structure; Groyas Semi group, Monoid Groups, Abelian Group, properties of groups, Permutation Groups, Sub Group, Cyclic Group, Rings and Fields (definition and standard results).

Graphs:

Graph terminology, types of graph connected graphs, components of graph, Euler graph, Hamiltonian path and circuits, Graph coloring, Chromatic number. Tree: Definition, types of tree(rooted, binary),properties of trees, binary search tree, tree traversing (preorder, inorder, postorder).
Finite Automata:Basic concepts of Automation theory, Deterministic finite Automation(DFA), transition function, transition table, Non Deterministic Finite Automata (NDFA),Mealy and Moore Machine, Minimization of finite Automation.