NIT Srinagar Syllabus CSE 3rd Sem Discrete Structures

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:

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

Leave a Comment