Discrete Mathematics

Paper Code: 
25GBCA301
Credits: 
06
Periods/week: 
06
Max. Marks: 
100.00
Objective: 

Course Objectives:

The course will enable 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

 

25GBCA301

 

Discrete Mathematics (Theory)

CO163.Examine the application of set theory; Pigeonhole Principle, Principlesof Inclusion-Exclusion,

CO164. Apply Propositional logic and its principles.

CO165. Analyse and compute problems related to Boolean Algebra and Boolean functions.

CO166. Analyse the properties of different kinds of graphs/trees and their application.

CO167. Assimilate various graph theoretic concepts and familiarize with their applications.

CO168. 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,  Assignments, Presentation.

 

18.00
Unit I: 

Set Theory: Definition of Sets, Venn Diagrams, complements, Cartesian products, power sets, counting principle, cardinality and countability (Countable and Uncountable sets), proofs  of some general identities on sets, Permutations and Combinations, Pigeonhole Principle, Principles of Inclusion-Exclusion, Mathematical induction, Recurrence relation.

 

18.00
Unit II: 

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.

 

18.00
Unit III: 

Ordered Relations & Structures: Partially orderd sets, external elements of partially ordered sets, Lattices & Boolean Algebra: Relation to partial ordering, lattices, HasseDiagram, Axiomatic definition  of  Boolean  algebra  as  algebraic  structures  with  two  operations  basic  results truthvalues and truth tables, the algebra of propositional functions, Boolean algebra of truth values, Applications (Switching Circuit, Gate Circuit).

 

18.00
Unit IV: 

Relation & Diagraphs: Product sets & Partitions, Relations & diagraphs, paths in relation & diagraphs, properties of relations, Equivalence relations, manipulation of relations.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).

 

 

 

Unit V: 

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, Minima's Path Application (Flow charts and state transition Graphs, Algorithm for determining cycle and minimal paths), Graph coloring, shortest path algorithm (Djikstras algorithm).

 

ESSENTIAL READINGS: 

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‐Hill Internatio          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”,           GalgotiaPublications 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.

 

Academic Year: