Log in Sign up

CS-302 Discrete Structure Notes

8 notes for Discrete Structure, unit by unit.

Unit 1 · Short notes Set Theory, Relations, Functions, and Theorem Proving Techniques Definition of sets, countable and uncountable sets · Venn diagrams and proofs of general set identities · Definition and types of relations, composition of relations, pictorial representation · Equivalence relations and partial ordering relations; Job‑scheduling problem · Definition and types of functions, one‑to‑one, onto, into, inverse functions, composition of functions · Recursively defined functions and the pigeonhole principle
Unit 2 · Short notes Algebraic Structures Definition and properties of semigroups and monoids · Groups, Abelian groups, subgroup, cyclic groups, cosets, factor groups · Permutation groups, normal subgroups, homomorphism and isomorphism of groups · Rings and fields: definitions and standard results
Unit 3 · Short notes Propositional and First‑Order Logic Propositions, predicates, and quantifiers (universal and existential) · Basic logical operations, truth tables, tautologies and contradictions · Algebra of propositions, logical implications and equivalence · Normal forms (CNF, DNF) and logical equivalences
Unit 4 · Short notes Finite State Machines Finite state machines as models of physical systems · Equivalence of finite state machines · Finite state machines as language recognizers
Unit 5 · Short notes Graph Theory Basic terminology of graphs, planar graphs, multigraphs and weighted graphs · Isomorphic graphs, paths, cycles and connectivity · Shortest path algorithms in weighted graphs · Eulerian paths and circuits, Hamiltonian paths and circuits · Graph coloring, chromatic number · Isomorphism and homomorphism of graphs
Unit 6 · Short notes Posets, Hasse Diagrams and Lattices Ordered sets and Hasse diagrams · Isomorphic and well‑ordered sets · Properties of lattices, bounded and complemented lattices
Unit 7 · Short notes Combinatorics Permutations and combinations · Binomial theorem and multinomial coefficients
Unit 8 · Short notes Recurrence Relations and Generating Functions Introduction to recurrence relations and recursive algorithms · Linear recurrence relations with constant coefficients: homogeneous and particular solutions · Total solutions of recurrence relations · Generating functions and solution by the method of generating functions

More for CS-302

Discrete Structure subject page

Other 3rd semester CSE subjects

All CSE 3rd semester subjects