CSPC-411 Discrete Mathematics | |||||||
|---|---|---|---|---|---|---|---|
Teaching Scheme | Credit | Marks Distribution | Duration of End Semester Examination | ||||
| L | T | P | Internal Assessment | End Semester Examination | Total | ||
| 3 | 0 | 0 | 3 | Maximum Marks: 40 | Maximum Marks: 60 | 100 | 3 Hours |
| Minimum Marks: 16 | Minimum Marks: 24 | 40 | |||||
Unit-I
Sets, Relations and Functions: Operations on Set, Inclusion -exclusion principle, Representation of Discrete Structures, Fuzzy Set, Multi-set, bijective function, Inverse and Composition of functions, Floor and Ceiling functions, Growth of functions: Big-O notation, functions, Recursive function, Functions applications.
Unit-II
Relations: Reflexivity, Symmetry, transitivity, Equivalence, and partial ordered relations, Asymmetric, Irreflexivity relation, Inverse and Complementary relations, partitions and Covering of a set, N-ary Relations and database, Representation relation using matrices and digraph, Closure of relations, Warshall's algorithms, Lexicographic Ordering, Hasse diagram, Lattices, Boolean algebra, Application of transitive Closure in medicine and engineering. Application: Embedding a partial order.
Unit-III
Graph Theory: Representation, Type of Graphs, Paths, and Circuits: Euler Graphs, Hamiltonians Paths & Circuits: Cut Sets, Connectivity and Separability, Planar Graphs, Isomorphisms, Graph Coloring, Covering and Partitioning, Max flow: Ford -Fulkerson algorithm, Application of Graph Theory in real life applications.
Basic Logic: Propositional Logic, Logical connectives, Truth Tables, Normal Forms (Conjunctive and Disjunctive), Validity of well-formed formula, Propositional inference rules (Concepts of modus ponens and modus tollens), Predicate Logic, Universal and existential quantification.
Unit-IV
Proof Techniques and Counting: notions of Implications, equivalence, converse, inverse, contra positive, negation and contradiction, The structure of mathematical proofs, Direct proofs, disproving by counter example, Proof by contradiction, Induction over natural numbers, structural induction, weak and strong induction, The pigeonhole principle, solving homogenous and heterogenous recurrence relations.
Algebraic Structure: Group, Semi-group, Monoids, Homomorphism, Congruencies, Ring, Field, Homomorphism, Congruencies, Applications of algebra to control structure of a program, the application of Residue Arithmetic to Computers.