Scribd
Upload
67 views

DMGT Course Plan

Uploaded by

keshav.aga12
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
67 views

DMGT Course Plan

Uploaded by

keshav.aga12
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Indian Institute of Information Technology, Nagpur

Academic Year 2022-2023 (Even Semester)


Course Plan
Discrete Mathematics and Graph Theory (CSL 204)

Module 1

1. Introduction to course - Syllabus, outcomes, evaluation strategy, exam pattern

2. Introduction to set theory: Set definition, Types of sets, Set representation: Venn
diagram, Subsets, Cardinality of set

3. Power Set, cartesian product, Set operations: Union, Intersection, Subtraction,


Complement.

4. Set Identities and their proofs.

5. Generalized Union and Intersections, Computer representation of sets

6. Introduction to relations, Relations on set,

7. Properties of relations: Reflexive, Irreflexive, Symmetric, Asymmetric,


Anti-symmetric, transitive.

8. Composition of relation - Combining relations

9. Equivalence Relation, Partial Orderings

10. Closures - Transitive - Warshall’s Algorithm, Symmetric, Reflexive

Module 2

1. Algebraic Structures: Definition, Properties

2. Types: Semi Groups, Monoid, Groups, Abelian group,

3. Types: Semi Groups, Monoid Groups, Abelian groups Continued…

4. Properties of groups

5. Subgroup, cyclic groups, Cosets, factor group, Permutation groups

6. Subgroup, cyclic groups, Cosets, factor group, Permutation groups Continued…

7. Normal subgroup, Homomorphism and isomorphism of Groups

8. Normal subgroup, Homomorphism and isomorphism of Groups Continued…

9. Rings and Fields: definition and standard results


10. Numericals on the algebraic structure

Module 3

1. Introduction to propositional logic

2. First order logic, Basic logical operation

3. Compound propositions, Truth tables

4. Tautology, contradiction, contingency

5. Algebra of propositions

6. Logical Equivalence

7. Normal Forms - CNF

8. Universal and existential quantifiers

9. Introduction to finite state machine

10. Finite state machines as language recognizers

Module 4

1. Graph Theory: Introduction and basic terminology of graphs.

2. Types of Graphs: Planar graphs, Multigraphs and weighted graphs, Isomorphic


graphs

3. Paths, Cycles and connectivity, Shortest path in weighted graph.

4. Introduction to Eulerian paths and circuits

5. Hamiltonian paths and circuits

6. Graph coloring, chromatic number, Isomorphism and Homomorphism of graphs.

7. Hypergraphs, transitive closure

8. Introduction to trees, spanning trees.

9. Connectivity, Colorability, Line Graphs

Module 5

1. Introduction: Posets, Hasse Diagram and Lattices

2. ordered set, Hasse diagram of partially, ordered set,

3. isomorphic ordered set, well ordered set


4. properties of Lattices

5. bounded and complemented lattices.

6. Combinatorics: Introduction, Permutation and combination.

7. Binomial Theorem, Multimonial Coefficients

8. Recurrence Relation and Generating Function, Recurrence Relation and Recursive


algorithms

9. Linear recurrence relations with constant coefficients,

10. Homogeneous solutions, Particular solutions, Total solutions .

Evaluation Plan

Sr. No Evaluation based on Weightage

1. Sessional exam 1 15 Marks

2. Sessional exam 2 15 Marks

3. End semester exam 50 Marks

4. Quizzes - 2 20 Marks

5. Tutorial - Exam 25 Marks

Dr. Nileshchandra Kalbarao Pikle


Assistant Professor, CSE Department,
IIIT Nagpur, MS

You might also like