Discrete Mathematics (CSC301)
1 unit: · L-T-P 3-1-0.
Detailed syllabus
Unit 1
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, pigeonhole principle. 3L Relation: Definition, types of relation (reflexive, symmetric, transitive, antisymmetric, Equivalence, partial ordering relations), composition of relations, domain and range of a relation, pictorial representation of relation, properties of relation, Partial Order, Lattice, Hasse Diagram. 6L Function: Definition and types of function, composition of functions, recursively defined functions, Surjection, Injection, Bijection, Composition of Function, Asymptotic notations: big-Oh, Theta, big-Omega. 4L 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 Well ordering principle. 6L Combinatorics: Mathematical induction, recursive mathematical definitions, basics of counting, permutations, combinations, inclusion-exclusion, recurrence relations (nth order recurrence relation with constant coefficients, Homogeneous recurrence relations), generating function (closed form expression, properties of G.F., solution of recurrence relation using G.F, solution of combinatorial problem using G.F.) 8L Algebraic Structure: Binary composition and its properties definition of algebraic structure; Semi group, Monoid, Groups, Abelian Group, properties of groups, Permutation Groups, Sub Group, Cyclic Group. 6L Graphs: Graph terminology, types of graph, connected graphs, components of graph, Euler graph, Hamiltonian path and circuits, Degree Sequence, Radius, Diameter, Center of a graph, Graph
Source: official document