DISCRETE MATHEMATICS (CS 601)

DISCRETE MATHEMATICS




UNIT -I

Fundamentals Of Logic:

      Basic connectives and Truth Tables
      Logical Equivalence
      Logical Implication
      Use of Quantifiers
      Definitions and the Proff of Theorems

Boolean Algebra:

      Switching Functions
      Logic Gates
      Don't Care Conditions

Set Theory:

      Sets and Subsets
      Set Operations and laws of set Theory
      Counting and Venn Diagrams.


UNIT-II

Proprties Of Integers:

      The Well-Ordering principle
      Recursive definitions
      The Division Algorithm
      Euclidean Algorithm
      Fundamental theorem of arithmetic.

Functions:

      Cartesian Product
      Functions
      Onto Functions
      Spetial Functions
      Pigeonhole Principle
      Composition and Inverse Functions
      Computational Complexity

Relations: 

      Partial Order Relations
      Lattices
      Equivalence Relations and Partitions



UNIT-III

Principle of Inclusion and Exclusion:

      Principles of Inclusion and Exclusion
      Generalization of principle,
      Defragments
      Rooks Polynomials
      Arrangements with Forbidden Positions

Generating Functions:

      Introductory examples
      Definitions and eamples
      Partition of Integers
      Exponential generating Function
      Summation operator

UNIT-IV

Recurrence Relations:

      First order Linear Recurrence Relation
      Second order Linear Homogeneous Recurrence Relations with constant coefficients
      Non homogeneous recurrence relations
      Devide and conquer algorithms

Algebraic Structures:

      Definitions
      Examples and elementary properties
      Homomorphism
      Isomorphism and Cyclic groups


UNIT-v

Graph Theory:

      Definitions and examples
      SubGraphs
      Complements and Graph Isomorphism
      Vertex Degree
      Planar grphs:
      Hamiltonian paths and Cycles
      Graph coloring

Trees:
  
      Definitions
      Properties and examples
      Rooted Trees
      Spaning Trees and
      Minimum Spaning Trees.



Suggested Reading

1. Raiph P.Grimaldi, "Discrete Mathematics and its Applications" Tata McGraw Hill, 6th Edition,2007

2. J.P Tremblay & R.Mnohar, "Discrete Mathematical Structures with Applications to computer science" Mc Graw Hill.1947

3. Joe L mott, A.kandal & T.p Baker, "Discrete Mathematics for computer scientists & Mathematicians", Prentice Hall N.J,1986

4. Kevin Ferland, "Discrete Mathematics", Houghton Mifflin Company,2009.