Discrete Structure
The complete RGPV syllabus for Discrete Structure (CS302), the third-semester mathematics course for B.Tech Computer Science & Engineering under the AICTE Flexible Curricula — set theory, algebraic structures, propositional logic and finite-state machines, graph theory, lattices, and combinatorics with recurrence relations and generating functions.
Discrete Structure
by Dr. D.C. Agarwal · ₹400 — covers this full RGPV syllabus.
Course contents — unit by unit
Unit 1 · Set Theory, Relations, Functions & Theorem-Proving Techniques
Set theory — definition of sets, countable and uncountable sets, Venn diagrams, proofs of general identities. Relations — types, composition, pictorial representation, equivalence and partial-ordering relations, job-scheduling problem. Functions — one-to-one/into/onto, inverse, composition, recursively defined functions, pigeonhole principle. Theorem proving — mathematical induction, proof by contradiction.
Unit 2 · Algebraic Structures
Definition, properties and types — semigroups, monoids, groups, abelian groups, subgroups, cyclic groups, cosets, factor groups, permutation groups, normal subgroups, homomorphism and isomorphism of groups; rings and fields (definition and standard results).
Unit 3 · Propositional Logic & Finite State Machines
Propositional logic — proposition, first-order logic, logical operations, truth tables, tautologies and contradictions, algebra of propositions, logical implication and equivalence, predicates, normal forms, quantifiers. Finite state machines as models of physical systems, equivalence machines, and as language recognizers.
Unit 4 · Graph Theory, Posets & Lattices
Graphs — terminology, planar/multi/weighted graphs, isomorphism, paths, cycles and connectivity, shortest path, Eulerian and Hamiltonian paths and circuits, graph colouring and chromatic number. Posets, Hasse diagrams and lattices — ordered sets, isomorphic and well-ordered sets, properties of lattices, bounded and complemented lattices.
Unit 5 · Combinatorics, Recurrence Relations & Generating Functions
Permutations and combinations, binomial theorem, multinomial coefficients. Recurrence relations and recursive algorithms, linear recurrence with constant coefficients, homogeneous, particular and total solutions, generating functions and solution by generating functions.