Discrete Mathematics Syllabus

Unit	Details
I	Introduction: Variables, The Language of Sets, The Language of Relations and Function Set Theory: Definitions and the Element Method of Proof, Properties of Sets, Disproofs, Algebraic Proofs, Boolean Algebras, Russell’s Paradox and the Halting Problem. The Logic of Compound Statements: Logical Form and Logical Equivalence, Conditional Statements, Valid and Invalid Arguments
II	Quantified Statements: Predicates and Quantified Statements, Statements with Multiple Quantifiers, Arguments with Quantified Statements Elementary Number Theory and Methods of Proof: Introduction to Direct Proofs, Rational Numbers, Divisibility, Division into Cases and the Quotient-Remainder Theorem, Floor and Ceiling, Indirect Argument: Contradiction and Contraposition, Two Classical Theorems, Applications in algorithms.
III	Sequences, Mathematical Induction, and Recursion: Sequences, Mathematical Induction, Strong Mathematical Induction and the Well-Ordering Principle for the Integers, Correctness of algorithms, defining sequences recursively, solving recurrence relations by iteration, Second order linear homogenous recurrence relations with constant coefficients. general recursive definitions and structural induction. Functions: Functions Defined on General Sets, One-to-One and Onto, Inverse Functions, Composition of Functions, Cardinality with Applications to Computability
IV	Relations: Relations on Sets, Reflexivity, Symmetry, and Transitivity, Equivalence Relations, Partial Order Relations Graphs and Trees: Definitions and Basic Properties, Trails, Paths, and Circuits, Matrix Representations of Graphs, Isomorphism’s of Graphs, Trees, Rooted Trees, Isomorphism’s of Graphs, Spanning trees and shortest paths.
V	Counting and Probability: Introduction, Possibility Trees and the Multiplication Rule, Possibility Trees and the Multiplication Rule, Counting Elements of Disjoint Sets: The Addition Rule, The Pigeonhole Principle, Counting Subsets of a Set: Combinations, r-Combinations with Repetition Allowed, Probability Axioms and Expected Value, Conditional Probability, Bayes’ Formula, and Independent Events.

Discrete Mathematics Practicals

Practical No	Details
1	Set Theory
a	Inclusion Exclusion principle.
b	Power Sets
c	Mathematical Induction
2	Functions and Algorithms
a	Recursively defined functions
b	Cardinality
c	Polynomial evaluation
c	Greatest Common Divisor
3	Counting
a	Sum rule principle
b	Product rule principle
c	Factorial
d	Binomial coefficients
e	Permutations
f	Permutations with repetitions
g	Combinations
h	Combinations with repetitions
i	Ordered partitions
j	Unordered partitions
4	Probability Theory
a	Sample space and events
b	Finite probability spaces
c	Equiprobable spaces
d	Addition Principle
e	Conditional Probability
f	Multiplication theorem for conditional probability
g	Independent events
h	Repeated trials with two outcomes
5	Graph Theory
a	Paths and connectivity
b	Minimum spanning tree
c	Isomorphism
6	Directed Graphs
a	Adjacency matrix
b	Path matrix
7	Properties of integers
a	Division algorithm
b	Primes
c	Euclidean algorithm
d	Fundamental theorem of arithmetic
e	Congruence relation
f	Linear congruence equation
8	Algebraic Systems
a	Properties of operations
b	Roots of polynomials
9	Boolean Algebra
a	Basic definitions in Boolean Algebra
b	Boolean algebra as lattices
10	Recurrence relations
a	Linear homogeneous recurrence relations with constant coefficients
b	Solving linear homogeneous recurrence relations with constant coefficients
c	Solving general homogeneous linear recurrence relations

Discrete Mathematics Reference Books