Discrete Structures & Optimization Notes
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/
Subject at a glance
4
Units
35
Topics
4
Credits
4
Infographics
Unit-wise Syllabus
4 units — open any unit for detailed topic-wise notes, diagrams and important exam questions
- 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)
Reflexive
a R a for every a
Equals, ≤
Symmetric
a R b means b R a
Equals, 'is a sibling of'
Antisymmetric
a R b and b R a means a = b
≤
Transitive
a R b and b R c means a R c
<, ≤, equals
Study guide
This unit covers set combinations and identities, relations (equivalence and partial order), hashing functions, rings, subrings, ideals, quotient rings, Euclidean and integral domains, fields and Boolean algebra with its applications in logic gates and Karnaugh maps. Practise proving set identities with membership tables.
- Basic counting principles
- permutations and combinations
- inclusion-exclusion principle
- recurrence relations
- generating functions
- pigeonhole principle and applications
Permutations
nPr = n! / (n − r)!
Combinations
nCr = n! / [r! (n − r)!]
Inclusion-exclusion
n(A ∪ B ∪ C) = Σ n(A) − Σ n(A ∩ B) + n(A ∩ B ∩ C)
Pigeonhole principle
n + 1 items in n boxes: some box has two or more
Study guide
You study counting: basic principles, permutations and combinations, inclusion-exclusion, recurrence relations, generating functions and the pigeonhole principle. Work many counting problems; the skill is choosing the right principle.
- Groups
- semigroups and monoids
- cyclic semigroups and submonoids
- subgroups and cosets
- congruence relations on semigroups
- morphisms
- normal subgroups
- dihedral groups
- Abelian group
Group + commutative
- Group
Monoid + every element has an inverse
- Monoid
Semigroup + identity element
- Semigroup
Closed and associative
Study guide
You study groups, semigroups and monoids, cyclic semigroups, subgroups and cosets, congruences, morphisms, normal subgroups and dihedral groups. Check the group axioms systematically on each example.
- 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
- Euler circuit
- Uses every edge once: all degrees even
- Hamiltonian cycle
- Visits every vertex once
- Chromatic number
- Fewest colours with no adjacent pair alike
- Planar graph
- Drawn without crossing edges: V − E + F = 2
- Isomorphic graphs
- Same structure, different labels
Study guide
You study directed and undirected graphs, Eulerian and Hamiltonian paths, trees, chromatic number, connectivity, colouring, planar graphs, isomorphism and applications. Draw each graph and test the properties.
Why Discrete Structures & Optimization Matters
Discrete structures are the mathematical backbone of algorithms, cryptography, databases and networks, and they are central to computer science research and exams such as GATE.
How to Prepare for Discrete Structures & Optimization
- Practise proofs and counting problems regularly.
- Draw diagrams for relations, groups and graphs.
- Connect each topic to a computing application.
Discrete Structures & Optimization: Frequently Asked Questions
Why study groups and rings in computer science?
They underpin cryptography, coding theory and algorithm design, where algebraic structures describe how operations behave.