BITM Discrete Mathematics and Its Applications Syllabus

Course Contents	Teaching Methodology	Teaching Hours
Unit 1: The Foundations: Logic and Proof
Logic: Propositions, Proposition variables, Truth table, conjunction, disjunction, Exclusive, implications, converse, inverse, Contra positive, Bi-conditional, Tautology, Contradiction, translating English sentences, logic and bit operations	Lecture
Propositional Equivalences: Introduction, Logical equivalences: Identity law, Domination law, Idempotent laws, Double negation law, commutative law, associative law, Distributive law, De-Morgan's law, Absorption law, Negation law (Verification)
Brief introduction and examples of Predicates and Quantifiers
Methods of Proof: Methods of proving theorems (direct proofs, indirect proofs, vacuous and trivial proofs, proof by contradiction).
Unit 2: The Fundamentals: Algorithms, the Integers, and Matrices
Algorithms: Introduction, searching algorithms (linear, binary), sorting (bubble, insertion), greedy algorithms, halting problem	Lecture
The Growth of Functions: Introduction, big-O notation, the growth of combinations of functions, big-omega and big-theta notation
Complexity of Algorithms: Introduction, time complexity, worst case complexity, average case complexity, understanding the complexity of algorithms
The Integers and Division: Introduction, division, primes, the fundamental theorem of arithmetic, the infinitude of primes, the division algorithm, GCD and LCM, modular arithmetic, applications of congruence's, Cryptology.
Unit 3: Mathematical Reasoning, Induction, and Recursion
Sequences and Summations: Introduction, sequences, recurrence relations, special integer sequences, summations	Lecture
Mathematical Induction: Introduction, mathematical induction, Recursive Definitions. Introduction, recursively defined function
Recursive Algorithms, recursion and iteration, the merge sort
Unit 4: Counting
Basic counting principle – The sum rule and the product rule.	Lecture
Permutation of n different objects, The number of r – permutations of n distinct objects when (a) repetition of objects are not allowed (b) repetition of objects are allowed. Permutations of n objects when the things are not distinct, circular permutations. Restricted permutations – The number of r-permutations of n different objects in which (i) k particular objects do not occur and (ii) k particular objects are always present.
Combination: r-combinations of n different objects, Restricted combinations, combinations with repetitions: the number of combinations of n objects taken r at a time with repetition is c(n+r-1, r)
Binomial Theorem, Binomial coefficients and Pascal triangle, Pascal's identity.
The pigeonhole principle and Inclusion and Exclusion principle.
Recurrence relation and solving it.
Unit 5: Relations and Functions
Product sets, Binary relations, Domain and Range of binary relation.	Lecture
Types of relations – Inverse relation, Identity relation, universe relations, void relation, complementary relation, ternary relation and n-ary relation.
Representation of relations – Table of relation, Arrow diagrams of relation, Graph of relation, Matrix of relation, Directed graph of a relation on a set A.
Boolean matrix, Boolean matrix operation, Boolean product of two matrices, complement of Boolean matrix.
Properties of relations – reflexive, irreflexive, symmetric, asymmetric, anti-symmetric and transitive relations. Equivalence relation, Equivalence relation and partition, Equivalence classes and quotient set. Partial order relation, Partial ordered set
Composition of two relations, matrix of composition relations properties – (a) If R is a relation from A to B and S a relation from B to C, then M(SoR) = M(R) ¤ M(S) (without proof); (b) If R is a relation from A to B, S a relation from B to C, and T a relation from C to D, then To(S o R) = (T o S) o R (without proof); (c) Let A, B and C be sets, R a relation from A to B, and S a relation from B to C. Then (S o R)^-1 = R^-1 o S^-1 (without proof)
Concept of function, Domain and Range, image and pre-image, Graph of a function f : A → B, Equality of functions, Real valued function, constant function and Identity function. Special functions – Floor function, ceiling function
Types of functions – onto function, one-to-one function, one-to-one correspondence between A and B, Inverse function.
The composition of two functions, Properties – (a) I(B)of = f, (b) foI(A) = f, (c) f^-1 of = I(A), (d) fof^-1 = I(B) (with proof), (f) (gof)^-1 = f^-1 og^-1.
Unit 6: Graphs
Introduction to Graphs and graph terminologies: Simple graph, multiple graph and pseudo graph, order of a graph and size of a graph, adjacent vertices, adjacent edges, degree of a vertex, isolated vertex and Pendant vertex. Degree sequence of a graph. Properties (with proofs): (a) The sum of the degree of the vertices of a graph is equal to twice the number of edges; (b) The number of odd vertices in a graph is always even. Special types of simple graph – Isolated graph, complete graph, Regular graph, Path graph, Cycle graph, Wheel graph, Bipartite graph and complete bipartite graph, Graphs of regular Platonic Solids. Properties (with proofs): (a) The total number of edges in a complete graph Kn is n(n-1)/2; (b) The number of vertices in a r-regular graph is even if r is odd; (c) The complete graph Kn is the regular graph of degree n – 1; (d) In the cyclic graph Cn, size of Cn is equal to order of Cn; (e) The size of wheel Wn is twice the size of Cn; (f) The sum of the degrees of vertices in Wn is four times the size of Cn; (g) Size of the complete bipartite graph Km,n is m × n and order is m + n.	Lecture
Representing Graphs: Adjacency list, Adjacency matrix, and Incidence matrix.
Isomorphism of Graph: Isomorphic graphs, Isomorphism classes, Self Complementary.
Connectivity: walk, trial and circuit, Path and Cycle, Connected graph, Cut-sets and Cut-vertices. Edge connectivity and vertex connectivity.
Euler and Hamilton Paths: Eulerian trial, Eulerian Circuit, Eulerian graph, Konigsberg Bridge problem. Theorems (without proofs): (a) A co…; (b) A connected graph G has Eulerian trial if and only if it has exactly two odd vertices. Hamiltonian path, Hamiltonian cycle and Hamiltonian graph. Theorems (without proofs): (a) (Ore's) A connected graph with n vertices is Hamiltonian if for any two non-adjacent vertices u and v, deg (u) + deg (v) ≥ n; (b) (Dirac) A connected graph with n(>2) vertices is Hamiltonian if degree of every vertex is at least n/2. Labeled graphs and weighted graphs
Shortest-Path Problems: Dijkstra's algorithm
Digraph, Simple digraph, Reflexive, Symmetric and Transitive digraph, Loop and parallel arc (edge), adjacent vertices and degree of vertices, Source vertex and Sink vertex. Theorem (without proof) – In a digraph, the sum of the in-degrees of vertices, the sum of the out-degrees of vertices and the number of edges are equal to each other.
Representation of digraph - Adjacency list, Adjacency matrix and Incidence matrix.
Connectivity of digraphs – underlying graph, directed walk, closed walk, directed path, directed cycle, spanning path. Weakly connected, unilaterally connected and strongly connected theorems (without proofs): (a) A diagraph D is unilaterally connected if it has a spanning path in D; (b) A diagraph D is strongly connected if it has a closed spanning path in D.
Unit 7: Trees
Introduction, rooted tree, non-rooted tree, root vertex, Terminal vertex, Internal vertex, Level of a vertex, H…	Lecture
Properties of tree (with proofs): (a) Let G(V, E) be a loop-free undirected graph. Then G is a tree if there is a unique path between any two vertices of G; (b) A tree with n vertices has exactly n – 1 edges; (c) In any tree G, there are at least two pendant vertices; (d) A forest G with n vertices has n – k edges, where k is the number of components of G.
Spanning tree and Methods of constructing a spanning tree from a graph by (a) Breadth – first search and (b) Depth – first search (Backtracking), Determination of the number of spannin…
Minimum spanning tree – (a) Kruskal algorthm (b) Prim's algorithm.
Tree Traversal: In order, Pre-order, and post order traversal
Applications of Trees: Binary expression tree
Full binary tree and its properties: (a) The number of vertices n in a binary tree is always odd; (b) The number of pendant vertices of a binary tree with n vertices is ½ (n + 1); (c) The number of internal vertices in a binary tree is one less than the number of pendant vertices; (d) The maximum number of vertices possible in K-level binary tree is 2^0 + 2^1 + 2^2 + .. + 2^K ≥ n; (e) The minimum possible height of an n-vertex binary tree is min lmax = ⌈log2 (n + 1)⌉ - 1, where Lmax = max level of any vertex; (f) The maximum possible height of an n – vertex binary tree is max lmax = (n - 1)/2

BITM Discrete Mathematics and Its Applications

Discrete Mathematics and Its Applications

Course Description

Course Objective

Course Contents

Text Books

Reference Books