Discrete Mathematics Structure
4IT2-01 · Semester 4
0/100 topics
Course objective
Course scope
Course outcome
Definition of sets
Countable and uncountable sets
Set operations
Partition of set
Cardinality
Inclusion-Exclusion Principle
Addition Principle
Venn Diagrams
Proofs of identities on sets
Relation definition
Types of relations
Composition of relations
Pictorial representation of relations
Equivalence relation
Partial ordering relation
Job-Scheduling problem
Function definition
Types of functions
One-to-one function
Into and onto functions
Inverse functions
Composition of functions
Recursively defined functions
Pigeonhole Principle
Generalized Pigeonhole Principle
Mathematical induction
Proof by contradiction
Propositions
First-order logic
Basic logical operations
Truth tables
Tautologies
Contradictions
Algebra of Propositions
Logical implications
Logical equivalence
Predicates
Normal forms
Universal quantifiers
Existential quantifiers
2-way predicate logic
Finite state machines introduction
FSM as models of physical systems
Equivalence of finite state machines
FSM as language recognizers
Posets introduction
Ordered sets
Hasse diagram of partially ordered sets
Isomorphic ordered sets
Well-ordered sets
Properties of Lattices
Bounded lattices
Complemented lattices
Combinatorics introduction
Permutations and combinations
Binomial Theorem
Multinomial coefficients
Recurrence relations introduction
Recursive algorithms
Linear recurrence relations with constant coefficients
Homogeneous solutions
Particular solutions
Total solutions
Generating functions
Solving recurrence relations using generating functions
Semi Groups
Monoids
Groups
Abelian groups
Properties of groups
Subgroups
Cyclic groups
Cosets
Factor groups
Permutation groups
Normal subgroups
Homomorphism of groups
Isomorphism of groups
Rings definition and standard results
Fields definition and standard results
Basic terminology of graphs
Planar graphs
Multigraphs
Weighted graphs
Isomorphic graphs
Paths and cycles in graphs
Graph connectivity
Shortest path in weighted graphs
Eulerian paths and circuits
Hamiltonian paths and circuits
Graph coloring
Chromatic number
Isomorphism of graphs
Homomorphism of graphs
Graph matching
Vertex covering
Edge covering