Discrete Mathematics

Paper Code: 
25CBDA315
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

 

 

 

 

 

 

 

 

 

 

 

 

 

25CBDA

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 tea ching: Interactive Lectures, Discussi on,  Reading assignments,Dem onstration.

Learning activities for the students: S elf

learning assignme nts,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
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

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: 

1.   Bernard Kolmann,  Robert C.  Busby  and  Sharon Ross,  “Discrete Mathematical Structures”, Thirdedition, PHI, 1997.

2.   K. G.  Rosen:  “Discrete Mathematics  and   Its  Applications”,  McGRAW‐HillInternational  Edition,Mathematics Series.

3.   S.  Lipschutz,  Marc  Lars  Lipson,  “Discrete Mathematics”,  McGRAW‐HILL  International Editions,Schaum’s Series.

 

REFERENCES: 

SUGGESTED READINGS:

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: 
2025-26
  • Printer-friendly version