DISCRETE MATHEMATICS

Paper Code: 
CBDA 315
Credits: 
3
Periods/week: 
3
Max. Marks: 
100.00
Objective: 

This Course enables the students to

  1. Acquaint students with the basic concepts of discrete mathematics that are useful in studying and describing objects and problems in all branches of computer science.
  2. Use mathematically correct terminology and notation.

Course Outcomes (COs).

Course Outcome (at course  level)

Learning and teaching strategies

Assessment Strategies

On completion of this course, the students will;

CO126.Understand truth tables and apply the concept of logical equivalence, its relationship to equivalent Normal Forms. Apply rules in inference theory, and extend this to propositional calculus.

CO127. Solve problems related to Pigeonhole Principle, Principles of Inclusion-Exclusion, Mathematical induction,  Recurrence relations.

 CO128.Understand partially ordered sets, lattices and their types; analyse and solve problems related to Boolean algebra and Boolean functions.

CO129.Use graphs as representing relations, Identify isomorphism invariants of graphs, and algorithms for relations based on graphs.

CO130.Identify applications of graphs and trees in real world scenario.

Approach in teaching: Discussion, Demonstration, Action Research, Project. Learning activities for the students:

Field activities, Presentation, Giving tasks

Class test, Semester end examinations, Quiz, Solving problems in tutorials, Assignments, Presentation.

 

9.00
Unit I: 

Propositional logic: Proposition logic, basic logic, logical connectives, truth tables, tautologies, contradiction, normal forms (conjunctive and disjunctive), modus ponens and modus tollens, validity, predicate logic, universal and existential quantification. Notion of proof: proof by implication, converse, inverse, contrapositive, negation, and contradiction, direct proof, proof by using truth table, proof by counter example

9.00
Unit II: 

Pigeonhole Principle, Principles of Inclusion-Exclusion, Mathematical induction, Recurrence relation.

Relation & Diagraphs: Product sets & Partitions, Relations & diagraphs, paths in relation & diagraphs, properties of relations, Equivalence relations.

 

9.00
Unit III: 

Ordered Relations & Structures: Partially ordered sets, external elements of partially ordered sets, Lattices & Boolean Algebra: Relation to partial ordering, lattices, Hasse Diagram, Axiomatic definition of Boolean algebra as algebraic structures with two operations basic results truth values and truth tables, the algebra of propositional functions, Boolean algebra of truth values.

 

9.00
Unit IV: 

Graphs Theory: Introduction to graphs, Graph terminology, Representing Graphs and Graph Isomorphism, Connectivity. Directed and undirected graphs and their matrix representations, reachability, Chains, Circuits, Eulers paths and cycles, Hamiltonian paths and cycles.

 

9.00
Unit V: 

Minima's Path Application (Flow charts and state transition Graphs, Algorithm for determining cycle and minimal paths), Graph coloring, shortest path algorithm (Djikstras algorithm). Trees:  Introduction, labeled trees, m-ary trees, undirected trees, properties of tree, Trees, Binary trees, Binary search trees and traversals, Spanning tree, Minimal spanning tree (Prim’s algorithm).

 

ESSENTIAL READINGS: 
  1. Bernard Kolmann, Robert C. Busby and Sharon Ross, “Discrete Mathematical Structures”, Third edition, PHI, 1997.
  2. K. G. Rosen: “Discrete Mathematics and Its Applications”, McGRAW‐Hill International Edition, Mathematics Series.
  3. S. Lipschutz, Marc Lars Lipson, “Discrete Mathematics”, McGRAW‐HILL International Editions, Schaum’s Series.

 

 

REFERENCES: 
  1. A.Doerr, Kenneth Levaseur, “Applied Discrete Structures for Computer Sciences”, Galgotia Publications Pvt. Ltd.
  2. G.N. Purohit, “Graph Theory”, Jaipur Publishing House
  3. Babu Ram: “Discrete Mathematics and Its Applications”, Vinayaka Publications.
  4. C.L. Liu, “Discrete Mathematics and Its Applications”, McGrawHill International Edition, Mathematics Series.
  5. Trembley, “Discrete Mathematics and Its Applications”, Tata McGrawHill.

 

E-RESOURCES:

  • https://www.youtube.com/watch?v=p2b2Vb-cYCs
  • https://www.tutorialspoint.com/discrete_mathematics/index.htm
  •  https://nptel.ac.in/courses/106108227
  • https://nptel.ac.in/courses/106106094

JOURNALS:

 

Academic Year: 
2023-24
  • Printer-friendly version