Discrete Structures & Optimization
Subject Overview
Discrete Structures & Optimization covers sets, relations and functions with hashing applications, rings and Boolean algebra (with logic gate and Karnaugh map applications), combinatorial mathematics (counting, permutations, recurrence relations, the pigeonhole principle), and monoids, groups and graph theory including Eulerian/Hamiltonian cycles, trees and graph coloring. A 4-credit core theory paper.
Unit-wise Syllabus
4 units — click WhatsApp below to get the full notes for each
Unit 1: Sets, relations, rings and Boolean algebra
Combination of sets, ordered pairs, proofs of set identities, relations, hashing functions, equivalence and partial order relations, rings, subrings, morphisms, ideals and quotient rings, Euclidean domains, integral domains and fields, Boolean algebra and its applications (logic implications, logic gates, Karnaugh maps)
Unit 2: Combinatorics
Basic counting principles, permutations and combinations, inclusion-exclusion principle, recurrence relations, generating functions, pigeonhole principle and applications
Unit 3: Groups
Groups, semigroups and monoids, cyclic semigroups and submonoids, subgroups and cosets, congruence relations on semigroups, morphisms, normal subgroups, dihedral groups
Unit 4: Graph theory
Directed and undirected graphs, Eulerian and Hamiltonian chains and cycles, trees, chromatic number, connectivity, graph coloring, plane and connected graphs, isomorphism and homomorphism and their applications