# Discrete Mathematics and Its Applications Syllabus - BIM (TU)

### Module Objectives:

To understand the concepts: Mathematical Reasoning, Combinatorial Analysis, Discrete Structures, Algorithmic Thinking, and Applications.

### Contents:

Logic and Proof, Algorithms, the Integers, Mathematical Reasoning, Induction, and Recursion, Counting, Relations and functions, Graphs, Trees.

### Unit Contents

Detailed Course

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

##### 2           The Fundamentals: Algorithms, the Integers, and Matrices
• 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.

##### 3.           Mathematical Reasoning, Induction, and Recursion
• 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
##### 4.                Counting
• Basic counting principle – The sum rule and the product
• 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

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
• The pigeonhole principle and Inclusion and Exclusion principle. 6Recurrence relation and solving it.
##### 5.                Relations and Functions
• Product sets, Binary relations, Domain and Range of binary
• Types of relations – Inverse relation, Identity relation, universe relations, void relation, complementary relation, ternary relation and n-ary
• Representation of relations – Table of relation, Arrow diagrams of relation, Graph of relation, Matrix of relation, Directed graph of a relation on a set
• Boolean matrix, Boolean matrix operation, Boolean product of two matrices, complement of Boolean
• Properties of relations – reflexive, irreflexive, symmetric, asymmetric, anti-symmetric and transitive 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 –
1. If R is a relation from A to B and S a relation from B to C, then MSOR = MR ¤ M(without proof)
2. 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  R) = (T   S)                                 (without proof)
3. Let A, B and C be sets, R a relation from A to B, and S a relation from B to C. Then (S R) - 1= R-1  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
• The composition of two functions, Properties – (a) IBof = f, (b) foIA = f,  (c) f -1 of = IA,

(d) fof-1 = IB, (with proof) , (f) (gof)-1 = f-1og-1.

##### 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):
1. The sum of the degree of the vertices of a graph is equal to twice the number of
2. The number of odd vertices in a graph is always

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

1. The total number of edges in a complete graph Kn is

n (n -1) 2

1. The number of vertices in a r-regular graph is even if r is
2. The complete graph Kn is the regular graph of degree n –
3. In the cyclic graph Cn, size of Cn is equal to order of C
4. The size of wheel Wn is twice the size of Cn.
5. The sum of the degrees of vertices in Wn is four times the size of Cn.
6. Size of the complete bipartite graph Km, n is m ´ n and order is m +
• Isomorphism of Graph: Isomorphic graphs, Isomorphism classes, Self
• Connectivity: walk, trial and circuit, Path and Cycle, Connected graph, Cut-sets and Cut- Edge connectivity and vertex connectivity.
• Euler and Hamilton Paths:

Eulerian trial, Eulerian Circuit, Eulerian graph, Konigsberg Bridge problem. Theorems without proofs):- a. A co

1. A connected graph G has Eulerian trial if and only if it has exactly two odd vertices.

path, Hamiltonian cycle and Hamiltonian graph. Theorems (without proofs)

1. (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.
2. (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

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.

• 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):
1. A diagraph D is unilaterally connected if it has a spanning path in
2. A diagraph D is strongly connected if it has a closed spanning path in
##### 7.  Trees
• Introduction, rooted tree, non-rooted tree, root vertex, Terminal vertex, Internal vertex, Level of a vertex, H
1. 2 Properties of tree (with proofs).
1. Let G(V, E) be a loop-free undirected Then G is a tree if there is a unique path between any two vertices of G.
2. A tree with n vertices has exactly n – 1
3. In any tree G, there are at least two pendant
4. A forest G with n vertices has n – k edges, where k is the number of components of
• Spanning tree and Methods of constructing a spanning tree from a graph by
1. Breadth – first search and b) Depth – first search (Backtracking), Determination of the number of spanni
• Minimum spanning tree – a) Kruskal algorthm b) Prim's
• Tree Traversal: In order, Pre-order, and post order traversal
• Applications of Trees: Binary expression tree
• Full binary tree and its properties:
1. The number of vertices n in a binary tree is always
2. The number of pendant vertices of a binary tree with n vertices is ½ (n + 1).
3. The number of internal vertices in a binary tree is one less than the number of pendant
1. The maximum number of vertices possible in K-level binary tree is 20 + 21 + 22 + .. + 2K
2. The  minimum   possible   height   of   an          n-vertex binary   tree   is   min   lmax   =
 2

élog (n +1) -1ù , where Lmax = maxm level of any vertex.

1. The maximum possible height of an n – vertex binary tree is max lmax =

(n -1)

2

##### Lecture: 48 Hours

Tutorial: 12 Hours

### Text and Reference Books

###### Text Book

Rosen K.H., Discrete Mathematics and its applications, 5th Edition, McGraw Hill Companies

###### References

Kolma, Busby, Ross; Discrete Mathematical Structures, Prentice – Hall of India.

1. Joshnsonbaugh; Discrete Mathematics, Pearson Education Asia.

Seymour Lipschutz and Marc Lipson; Discrete Mathematics, (Schaum's Outline).