Department Events
DISCRETE MATHEMATICS
Course Objectives:
The course will enable the students to
- 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.
- Use mathematically correct terminology and notation
Course Outcomes (COs):
Learning Outcome (at course level)
| Learning and teaching strategies | Assessment Strategies |
CO 117 Understand partially ordered sets, lattices and their types. CO 118 Analyse and compute problems related to Boolean algebra and Boolean functions. CO 119 Assimilate various graph theoretic concepts and familiarize with their applications. CO 120 Solve problems related to Pigeonhole Principle, Principles of Inclusion-Exclusion, Mathematical induction, Recurrence relation. CO 121 Explain set theory and its applications. | Approach in teaching: Discussion, Demonstration, Action Research, Project. Learning activities for the students: Field activities, Simulation, Presentation, Giving tasks | Class test, Semester end examinations, Quiz, Solving problems in tutorials, Assignments, Presentation. |
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.
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.
Ordered Relations & Structures: Partially orderd 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, Applications (Switching Circuit, Gate Circuit).
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).
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).
- Bernard Kolmann, Robert C. Busby and Sharon Ross, “Discrete Mathematical Structures”, Third edition, PHI, 1997.
- K. G. Rosen: “Discrete Mathematics and Its Applications”, McGRAW‐Hill International Edition, Mathematics Series.
- S. Lipschutz, Marc Lars Lipson, “Discrete Mathematics”, McGRAW‐HILL International Editions, Schaum’s Series.
- A. Doerr, Kenneth Levaseur, “Applied Discrete Structures for Computer Sciences”, Galgotia Publications Pvt. Ltd.
- G.N. Purohit, “Graph Theory”, Jaipur Publishing House.
- Babu Ram: “Discrete Mathematics and Its Applications”, Vinayaka Publications.
- C.L. Liu, “Discrete Mathematics and Its Applications”, McGrawHill International Edition, Mathematics Series.
- Trembley, “Discrete Mathematics and Its Applications”, Tata McGrawHill.
