# NIT Jalandhar CSE Syllabus for Discrete structure

CS-201 DISCRETE STRUCTURES [3 1 0 4]

Set Theory: Definition of sets, countable and uncountable sets, Venn Diagrams, proofs of some general identities on sets Set Theory, Functions and Relations: Subsets, Power Set, Null Set, Singleton, Finite Set, Infinite Set, Universal Set, Disjoint Sets, Operation on Sets, Venn Diagrams, Cartesian Product of Sets, Partition of Sets, Concept of Relation & Properties of Relations, Different types of Relations, Tabular and Matrix Representation of Relations, Relations and Diagraphs, Composition of Relations, Functions and their different mappings, Composition of Function, Recursion and Recurrence Relations.

Algebraic Structures: Definition, Properties, types: Semi Groups, Monoid, Groups, Abelian group, properties of groups, Subgroup, cyclic groups, Cosets, factor group, Permutation groups, Normal subgroup, Homomorphism and isomorphism of Groups, example and standard results, Rings and Fields: definition and standard results.

Posets, Hasse Diagram and Lattices: Introduction, ordered set, Hasse diagram of partially, ordered set, isomorphic ordered set, well ordered set, properties of Lattices, bounded I and complemented lattices.

Boolean Algebra: Partial Ordering, Totally ordered Sets, Dual Order, Hasse Diagram Lexicographic Ordering, Cover of an Element, Least and Greatest Elements, Minimal and Maximal Elements ,Upper and Lower Bound , Well-Order Set, Binary and n-Ary Operations, Lattices, Atoms of a Boolean Algebra, Boolean Expressions, Applications of Boolean Algebra to Switching Theory.

Tree: Definition, Rooted tree, properties of trees, binary search tree, tree traversal.

Propositional Logic: Proposition, First order logic, Basic logical operation, truth tables, tautologies, Contradictions, Algebra of Proposition, logical implications, logical equivalence, predicates, Universal and existential quantifiers.

Combinatorics & Graphs: Recurrence Relation, Generating function., Simple graph, multi graph, graph terminology, representation of graphs, Bipartite, Regular, Planar and connected graphs, connected components in a graph, Euler graphs, Hamiltonian path and circuits, Graph coloring, chromatic number, isomorphism and Homomorphism of graphs.

BOOKS RECOMMENDED

1.

Liptschutz, Seymour, “ Discrete Mathematics”, McGraw Hill.

2.

Trembley, J.P & R. Manohar, “Discrete Mathematical Structure with Application to Computer Science”, McGraw Hill.

3.

Kenneth H. Rosen, “Discrete Mathematics and its applications”, McGraw Hill.

4.

Deo, Narsingh, “Graph Theory With application to Engineering and Computer.Science.”, PHI.

5.

Krishnamurthy, V., “Combinatorics Theory & Application”, East-West Press Pvt. Ltd., New Delhi.