Discrete Mathematics

 Unit- I Relations and Digraph  (9 hrs)

1.1          Product set and partitions

1.2          Binary relations and its types

1.3          Different methods  representing

 relations.

•             Relation as an order pairs

•             Relations as matrix

•             Relations as  directed graphs

•             Relations as an arrow  diagram

•             Relations as graph         

                1.4          Properties of relations:

•             Reflexive,

•             Symmetric

•             Asymmetric

•             Transitive

•             Equivalence relation

•             Partial order relations

1.5          Boolean matrix representation of

             Relations

•             Boolean matrix operation

•             Boolean products 

1.6          Composition of two relations

1.7        Operation on relations

1.8        Transitive closure and Warshall’s

             algorithm

 

Unit  II  Counting and Combinatories  ( 7 hrs)

               

2.1.Introduction  

2.2 Basic principles of counting

•             Sum rule principle

•             Product rule principle

2.3 Permutation of n- different objects

            2.4 Combination

2.5 The pigeonhole principle

2.6 The extended pigeonhole principle

 

 

 

 

Unit III The Fundamental Algorithms, and Matrices (9 hrs)

3.1          Algorithms

3.2          Complexity of algorithm

•             Time complexity

•             Understanding the Complexity of algorithm.

3.3          Searching algorithm:

•             Linear search

•             Binary search

3.4          Sorting

•             Bubble sort

•             Insertion sort

3.5          Matrices

•             Matrix arithmetic

•             Transpose of matrix

•             Power of matrices

 

Unit- IV Recursion on Sequence and Series (8 hrs)

 

4.1  Introduction

4.2 Sequence and summations

•             Arithmetic progression

•             Geometric progression

•             Harmonic progression

•             Relations and properties 

•             Recurrence relations

•             Use of series on summation notation

4.3   Solutions for recursive relations

4.4 Recursive algorithm, recursion and iteration, the merge sort. 

4.5   Recursively defined functions

 

Unit : V Special Types of Functions (6 hrs)

 

5.1 Floor and ceiling function

5.2 Characteristics functions

5.3 Integer value functions

5.4 Remainder function: modular arithmetic

5.5 Factorial function

 

 

Unit- VI  Geometric Transformation ( 9 hrs)

6.1 Geometric properties of plane linear  

       transformation

6.2  Isometric transformation

•             Reflection

•             Translation

•             Half turn

•             Rotation

•             Glide Reflection

6.3 Non isometric transformation

•             Dilation

•             Stretch

•             Shear

6.4 Matrix representation of isometric and

non- isometric transformations