Discrete Mathematics
CIC-205
Sets, Subsets, powerset, operations on sets, Propositional Logic, Rules of inferences in propositional logic, Quantifiers, Predicates and validity, Predicate Logic, normal forms, Proof Techniques- Direct Proof, Proof by Contraposition, and proof by contradiction, Principle of inclusion and exclusion, pigeonhole principle, permutation and combination, Principle of Well Ordering, principle of mathematical induction, principle of complete induction, Relation, properties of binary relation, equivalence relation and class, closures (symmetric, reflexive, and transitive).
Functions, Growth of functions, Permutation functions, Partially ordered sets, lattices, Boolean algebra, Minimization of Boolean Expressions, GCD, LCM, prime numbers, Recurrence relations, solution methods for linear, first-order recurrence relations with constant coefficients, generating functions, Analysis of Algorithms involving recurrence relations, solution method for a divide-and-conquer recurrence relation, Masters theorem (with proof).
Semi-group, Monoid, Groups, Group identity and uniqueness, inverse and its uniqueness, isomorphism and homomorphism, subgroups, Cosets and Lagrange’s theorem, Permutation group and Cayley’s theorem (without proof), Normal subgroup and quotient groups, Groups and Coding.
Graph Terminology, Planar graphs, Euler’s formula (proof), Euler and Hamiltonian path/circuit, Chromatic number of a graph, five color theorem (proof), Shortest path and minimal spanning trees and algorithms, Depth-first and breadth first search, trees associated with DFS & BFS, Connected components, Complexity Analysis of the graph MST.