BITM Discrete Mathematics and Its Applications

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. 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).

Algorithms: Introduction, searching algorithms (linear, binary), sorting (bubble, insertion), greedy algorithms, halting problem. 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.

Sequences and Summations: Introduction, sequences, recurrence relations, special integer sequences, summations. Mathematical Induction: Introduction, mathematical induction, Recursive Definitions. Introduction, recursively defined function. Recursive Algorithms, recursion and iteration, the merge sort.

Basic counting principle – The sum rule and the product rule. 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.

Product sets, Binary relations, Domain and Range of binary relation. 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.

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. 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.

Introduction, rooted tree, non-rooted tree, root vertex, Terminal vertex, Internal vertex, Level of a vertex, H…. 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.