Discrete Mathematical Structures

Propositional Logic: Statements, Connectives, Truth Tables, Tautologies, and Contradictions. Normal Forms (CNF, DNF). Predicate Logic: Quantifiers ( , ), Nested Quantifiers, and Inference Theory. Proof Techniques: Direct, Indirect (Contrapositive), Contradiction, and Mathematical Induction (Strong and Weak) with applications to algorithm correctness.

Set Theory: Operations, Power Sets, Principle of Inclusion-Exclusion. Relations: Properties (Reflexive, Symmetric, Transitive), Equivalence Relations and Partitions (Database foundations). Partial Order Relations: Posets, Hasse Diagrams, Lattices, and Chains. Functions: Injective, Surjective, Bijective, Inverse Functions, and the Pigeonhole Principle with applications to hashing.

Counting Principles: Permutations, Combinations, and Derangements. Binomial and Multinomial Theorems. Recurrence Relations: Generating Functions, Linear Recurrence Relations with Constant Coefficients (Homogeneous and Non-homogeneous). Solving recurrences for Algorithm Analysis (e.g., Fibonacci, Divide and Conquer complexity).

Fundamentals: Directed and Undirected graphs, Weighted graphs, Paths, Cycles, and Connectivity. Eulerian and Hamiltonian Paths (Network routing problems). Graph Representation (Adjacency Matrix/List). Planar Graphs and Graph Coloring (Map coloring, Register allocation). Isomorphism and Homomorphism. Shortest Path algorithms concepts (Dijkstra/Floyd-Warshall context).

Trees: Rooted Trees, Binary Search Trees, Spanning Trees (Prim’s and Kruskal’s logic), and Tree Traversals. Algebraic Structures: Groups, Subgroups, Cyclic Groups, Lagrange’s Theorem. Rings and Fields (Finite Fields). Introduction to Number Theory: Modular Arithmetic, Euclidean Algorithm, Fermat’s Little Theorem, and Euler’s Totient Function (Mathematical foundation for RSA Cryptography).