**NIT Srinagar Syllabus**

### 3th Semester Syllabus

### Discrete Structures

**Sets and Propositions**

Combinations of Sets, Finite and Infinite Sets, Unaccountably Infinite Sets, Mathematical Induction, Principle of Inclusion and Exclusion , Multisets, Propositions

**Computability and Formal Languages**

Ordered Sets, Languages, Phrase Structure Grammars, Types of Grammars and Languages

**Permutations, Combinations, and Discrete Probability**

The Rules of Sum and Product, Permutations, Combinations, Generation of Permutations and Combinations, Discrete Probability , Conditional Probability, Information and Mutual Information

**Relations and Functions**

A Relational Model for Data Bases, Properties of Binary Relations, Equivalence Relations and Partitions, Partial Ordering Relations and Lattices, Chains and Antichains, A Job-Scheduling Problem, Functions and the Pigeonhole Principle

**Graphs and Planar Graph**

Basis Terminology, Multigraphs and Weighted Graphs, Paths and Circuits, Shortest Paths in Weighted Graphs, Eulerian Paths and Circuits, Hamiltonian Paths and Circuits, The Traveling Salesperson Problem

**Trees and Cut-Sets**

Trees, Rooted Trees, Path Lengths in Rooted Trees, Prefix Codes, Binary Search Trees, Spanning Trees and Cut-Sets, Minimum Spanning Trees

**Finite State Machines**

Finite State Machines, Finite State Machines as Models of Physical System, Equivalent Machines, Finite State Machines and Language Recognizers

**Discrete Numeric Functions and Generating Functions**

Manipulation of Numeric Functions, Asymptotic Behavior of Numeric Functions, Generating Functions, Combinatorial Problem

**Recurrence Relations and Recursive Algorithms**

Recurrence Relations, Linear Recurrence Relations with Constant Coefficients, Homogenous Solutions, Particular Solution

**Group and Rings**

Groups, Subgroups, Generators and Evaluation of Powers, Cosets and Lagrange’s Theorem, Permutation Groups and Burnside’s Theorem, Codes and Group Codes, Isomorphisms and Automorphisms, Homomorphisms and Normal Subgroups, Rings, Integral Domains, and Fields

**Boolean Algebras**

Lattices and Algebraic Systems, Principle of Duality, Basic Properties of Algebraic System, Defined by Lattices, Distributive and Complemented Lattices, Boolean Lattices and Boolean Algebras, Uniqueness of Finite Boolean Algebras, Boolean Functions and Boolean Expressions, Propositional Calculus

#### Books Recommended:

- Elements of Discrete Mathematics by C.L. Liu Mc Graw Hill
- Discrete Mathematical Structures by Kolman B, Busby R. C, Ross S.C by Pearson Education
- Discrete Mathematical Structures: Theory & Applications by D.S Malik & M.K.Sen Thomson India Edition