Discrete Structures Guidelines and Practical List
Course Objective: The course aims to introduce the students to Boolean algebra, sets, relations, functions, principles of counting, and growth functions so that these concepts may be used effectively in other courses.
Discrete Structures Guidelines
Introduction: Sets – finite and infinite sets, uncountable infinite sets; functions, relations, properties of binary relations, closure, partial ordering relations; counting – Pigeonhole Principle, permutation and combination; mathematical induction, Principle of Inclusion and Exclusion.
Growth of Functions: asymptotic notations, summation formulas and properties, bounding summations, approximation by integrals.
Recurrence: recurrence relations, generating functions, linear recurrence relations with constant coefficients and their solution, recursion trees, Master Theorem.
Graph Theory: basic terminology, models and types, multi-graphs and weighted graphs, graph representation, graph isomorphism, connectivity, Euler and Hamiltonian Paths and Circuits, planar graphs, graph coloring, Trees, basic terminology and properties of Trees, introduction to spanning trees.
Propositional Logic: logical connectives, well-formed formulas, tautologies, equivalences, Inference Theory
Discrete Structures Reference Books:
- Mohapatra, & Liu, C. L. (2012). Elements of Discrete mathematics. 4th edition. McGraw Hill Education.
- Rosen, K. H. (2011). Discrete Mathematics and Its Applications. 7th edition. Tata McGraw Hill Education.