IT-302 Discrete Structure Notes
5 notes for Discrete Structure, unit by unit.
Notes for IT-302
- Unit 1 · Short notes Set Theory, Relation, Function, Theorem Proving Techniques Definition of sets, countable and uncountable sets, Venn diagrams, proofs of general identities on sets · Definition of relations, types of relation, composition of relations, pictorial representation, equivalence relation, partial ordering relation, job scheduling problem · Definition of functions, types of functions, one‑to‑one, into and onto functions, inverse function, composition of functions, recursively defined functions, pigeonhole principle · Theorem‑proving techniques: mathematical induction and proof by contradiction
- Unit 2 · Short notes Algebraic Structures Definition, properties and types: semigroups, monoid, groups, abelian groups, subgroup, cyclic groups, normal subgroup, homomorphism and isomorphism of groups; examples and standard results · Rings and fields: definition and standard results
- Unit 3 · Short notes Propositional Logic Proposition, first‑order logic, basic logical operations, truth tables, tautologies, contradictions, algebra of propositions, logical implications, logical equivalence, predicates, normal forms, universal and existential quantifiers · Introduction to finite‑state machines: FSMs as models of physical‑system equivalence machines and as language recognizers
- Unit 4 · Short notes Graph Theory Introduction and basic terminology of graphs, planar graphs, multigraphs and weighted graphs, isomorphic graphs · Paths, cycles and connectivity, shortest path in weighted graphs · Eulerian paths and circuits, Hamiltonian paths and circuits · Graph colouring, chromatic number, isomorphism and homomorphism of graphs
- Unit 5 · Short notes Posets, Hasse Diagram and Lattices Ordered sets, Hasse diagrams of partially ordered sets, isomorphic ordered sets, well‑ordered sets, properties of lattices, bounded and complemented lattices · Combinatorics: introduction, permutations and combinations, binomial theorem · Recurrence relations and generating functions: introduction to recurrence relations, linear recurrence relations with constant coefficients, homogeneous solutions, particular solutions, total solutions, generating functions, solving by the method of generating functions
More for IT-302
Other 3rd semester IT subjects
- ES-301 Energy & Environmental Engineering
- IT-303 Data Structure
- IT-304 Object Oriented Programming & Methodology
- IT-305 Digital Circuits and Systems
- IT-306 Java Programming Lab