## Syllabus

# UNIT- I

**Fundamentals of Logic**: Basic Connectives and Truth Tables, Logical Equivalence, Logical Implication, Use of Quantifiers, Definitions and the Proof of Theorems.

**Set Theory**: Set and Subsets, Set Operations, and the Laws of Set theory, Counting and Venn Diagrams.

**Properties of the Integers**: The well – ordering principle, Recursive Definitions, Division Algorithms, Fundamental theorem of Arithmetic.

# UNIT-II

**Relations and Functions**: Cartesian Product, Functions onto Functions, Special Functions, Pigeonhole Principle, Composition and Inverse Functions, Computational Complexity.

**Relations: **Partial Orders, Equivalence Relations and Partitions.

**Principle of Inclusion and Exclusion****: **Principles of Inclusion and Exclusion, Generalization of Principle, Derangements, Rock Polynomials, Arrangements with Forbidden Positions.

# UNIT–III

**Generating Functions****: **Introductory Examples, Definition And Examples, Partitions Of Integers, Exponential Generating Function, Summation Operator.

**Recurrence Relations****: **First – order linear recurrence relation, second – order linear homogenous recurrence relation with constant coefficients, Non homogenous recurrence relation, divide and conquer algorithms.

# UNIT-IV

**Algebraic Structures: **Algebraic System – General Properties, Semi Groups, Monoids, Homomorphism, Groups, Residue Arithmetic, Group Codes and their Applications.

# UNIT -V

**Graph Theory: **Definitions and examples, sub graphs, complements and graph Isomorphism, Vertex degree, Planar graphs, Hamiltonian paths and Cycles, Graph Coloring, Euler & Hamiltonian graphs, and Chromatic number.

**Trees: **Definitions, properties and Examples, Rooted Trees, Spanning Trees and Minimum Spanning Trees.