Discrete Mathematics (Theory)

Paper Code: 
24CBDA315
Credits: 
03
Periods/week: 
03
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: 

Course

Learning outcome

(at course level)

Learning and teaching strategies

Assessment Strategies

Course Code

Course

Title

24CBDA

315

Discrete Mathematics

(Theory)

 

CO151. Assess the concept of propositional calculus to provide a formal system for representing logical relationships.

CO152. Apply Pigeonhole Principle, Inclusion-Exclusion, Induction, and Recurrence to problem-solving.

 CO153. Analyse and solve problems on Boolean algebra, partially ordered sets and lattices.

CO154. Construct graphs to represent relations, identify isomorphism invariants.

CO155.Solve applications of graphs and trees in real world scenario.

CO156.Contribute effectively in course-specific interaction

Approach in teaching: Interactive Lectures, Discussion, Reading assignments, Demonstration.

 

Learning activities for the students: Self learning assignments, Effective questions, Seminar presentation.

 

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: 
Mathematical induction and Relation & Diagraphs:

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 and Trees:

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: 

SUGGESTED TEXT BOOKS

  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: 

SUGGESTED REFERENCE BOOKS

  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:

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

JOURNALS:

  1. https://www.sciencegate.app/keyword/445436

 

Academic Year: 
2024-25
  • Printer-friendly version