Department Events
Discrete Mathematics (Theory)
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 | Learning Outcome (at course level) | Learning and teaching strategies | Assessment Strategies | |
Course Code | Course Title | |||
24GBCA 301 | Discrete Mathematics (Theory)
| CO163.Examine the application of set theory; Pigeonhole Principle, Principles of 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. |
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, HasseDiagram, 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.
SUGGESTED READINGS:
- 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.
