DISCRETE MATHEMATICS AND GRAPH THEORY L T P C
20MA303
(Common to CSE, IT and AI&DS) 3 2 0 4
Nature of Course Basic Sciences
Pre requisites Mathematics – I & II for Computing Sciences
Course Objectives
The course is intended to
1. Introduce the concepts of mathematical logic for analyzing propositions.
2. Learn the basic concepts of combinatorics.
3. Provide the concepts of graph theory and solving problems in different fields of study.
4. Acquaint with the applications of algebraic structures.
5. Learn the concepts and significance of lattices and Boolean algebra in computer science
and engineering.
Course Outcomes
On successful completion of the course, students will be able to
Bloom's
Course Outcome
CO.No Level
CO1 Explain the mathematical arguments for logical connectives. Understand
CO2 Compute the techniques of combinatorial analysis. Apply
CO3 Interpret the graph theory to solve practical problems. Understand
Distinguish the properties of algebraic structures for groups, rings and
CO4 Understand
fields.
CO5 Illustrate the logical notations of lattices and Boolean algebra. Apply
Course Contents:
UNIT I Mathematical Logic 12
Propositions – Logical connectives – Compound propositions –Conditional and biconditional
propositions-Truth tables – Tautologies and contradictions- Contra positive – Logical equivalences
and implications –Normal forms –PCNF and PDNF – Rules of inference-Predicates- Statement
functions.
UNIT II Combinatorics 12
Mathematical induction – Strong induction and well ordering – The basics of counting – The
pigeonhole principle – Permutations and combinations – Recurrence relations – Solving linear
recurrence relations – Generating functions – Inclusion and exclusion principle and its applications.
UNIT III Graphs 12
Graphs and graph models – Graph terminology and special types of graphs – Matrix representation
of graphs and graph isomorphism – Connectivity – Euler and Hamilton paths-Coloring-Matchings
UNIT IV Algebraic Structures 12
Algebraic systems – Semi groups and monoids - Groups – Subgroups –Homomorphism‘s –Normal
subgroup and cosets –Lagrange‘s theorem – Definitions and examples of Rings and Fields.
UNIT V Lattices and Boolean Algebra 12
Partial ordering – Posets – Lattices as posets – Properties of lattices - Lattices as algebraic
systems – Some special lattices – Boolean algebra-Definition and Examples.
Total: 60 Periods
20MA303
(Common to CSE, IT and AI&DS) 3 2 0 4
Nature of Course Basic Sciences
Pre requisites Mathematics – I & II for Computing Sciences
Course Objectives
The course is intended to
1. Introduce the concepts of mathematical logic for analyzing propositions.
2. Learn the basic concepts of combinatorics.
3. Provide the concepts of graph theory and solving problems in different fields of study.
4. Acquaint with the applications of algebraic structures.
5. Learn the concepts and significance of lattices and Boolean algebra in computer science
and engineering.
Course Outcomes
On successful completion of the course, students will be able to
Bloom's
Course Outcome
CO.No Level
CO1 Explain the mathematical arguments for logical connectives. Understand
CO2 Compute the techniques of combinatorial analysis. Apply
CO3 Interpret the graph theory to solve practical problems. Understand
Distinguish the properties of algebraic structures for groups, rings and
CO4 Understand
fields.
CO5 Illustrate the logical notations of lattices and Boolean algebra. Apply
Course Contents:
UNIT I Mathematical Logic 12
Propositions – Logical connectives – Compound propositions –Conditional and biconditional
propositions-Truth tables – Tautologies and contradictions- Contra positive – Logical equivalences
and implications –Normal forms –PCNF and PDNF – Rules of inference-Predicates- Statement
functions.
UNIT II Combinatorics 12
Mathematical induction – Strong induction and well ordering – The basics of counting – The
pigeonhole principle – Permutations and combinations – Recurrence relations – Solving linear
recurrence relations – Generating functions – Inclusion and exclusion principle and its applications.
UNIT III Graphs 12
Graphs and graph models – Graph terminology and special types of graphs – Matrix representation
of graphs and graph isomorphism – Connectivity – Euler and Hamilton paths-Coloring-Matchings
UNIT IV Algebraic Structures 12
Algebraic systems – Semi groups and monoids - Groups – Subgroups –Homomorphism‘s –Normal
subgroup and cosets –Lagrange‘s theorem – Definitions and examples of Rings and Fields.
UNIT V Lattices and Boolean Algebra 12
Partial ordering – Posets – Lattices as posets – Properties of lattices - Lattices as algebraic
systems – Some special lattices – Boolean algebra-Definition and Examples.
Total: 60 Periods
