Discrete Mathematics and Its Applications Syllabus  BIM (TU)
View and download full syllabus of Discrete Mathematics and Its Applications
Course Description
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, Biconditional, 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
 Logic
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, bigO notation, the growth of combinations of functions, bigomega 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 rpermutations of n different objects in which (i) k particular objects do not occur and (ii) k particular objects are always present.
 Combination:  rcombinations 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+r1, 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 nary
 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, antisymmetric 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 –
 If R is a relation from A to B and S a relation from B to C, then M_{SOR} = M_{R} ¤ M(without proof)
 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)
 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 preimage, 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, onetoone function, onetoone correspondence between A and B, Inverse
 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}.
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):
 The sum of the degree of the vertices of a graph is equal to twice the number of
 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):
 The total number of edges in a complete graph Kn is
n (n 1) 2
 The number of vertices in a rregular graph is even if r is
 The complete graph K_{n} is the regular graph of degree n –
 In the cyclic graph C_{n}, size of C_{n} is equal to order of C
 The size of wheel W_{n} is twice the size of C_{n}.
 The sum of the degrees of vertices in W_{n} is four times the size of C_{n}.
 Size of the complete bipartite graph Km, n is m ´ n and order is m +
 Representing Graphs: Adjacency list, Adjacency matrix, and Incidence
 Isomorphism of Graph: Isomorphic graphs, Isomorphism classes, Self
 Connectivity: walk, trial and circuit, Path and Cycle, Connected graph, Cutsets 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
 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)
 (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.
 (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,
 ShortestPath 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 indegrees of vertices, the sum of the outdegrees of vertices and the number of edges are equal to each other.
 Representation of digraph  Adjacency list, Adjacency matrix and Incidence
 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 diagraph D is unilaterally connected if it has a spanning path in
 A diagraph D is strongly connected if it has a closed spanning path in
7. Trees
 Introduction, rooted tree, nonrooted tree, root vertex, Terminal vertex, Internal vertex, Level of a vertex, H
 2 Properties of tree (with proofs).
 Let G(V, E) be a loopfree undirected Then G is a tree if there is a unique path between any two vertices of G.
 A tree with n vertices has exactly n – 1
 In any tree G, there are at least two pendant
 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
 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, Preorder, and post order traversal
 Applications of Trees: Binary expression tree
 Full binary tree and its properties:
 The number of vertices n in a binary tree is always
 The number of pendant vertices of a binary tree with n vertices is ½ (n + 1).
 The number of internal vertices in a binary tree is one less than the number of pendant
 Spanning tree and Methods of constructing a spanning tree from a graph by
 The maximum number of vertices possible in Klevel binary tree is 2^{0} + 2^{1} + 2^{2} + .. + 2^{K} ≥
 The minimum possible height of an nvertex binary tree is min l_{max} =

élog (n +1) 1ù , where L_{max} = max^{m} level of any vertex.
 The maximum possible height of an n – vertex binary tree is max l_{max} =
(n 1)
2
Lecture: 48 Hours
Tutorial: 12 Hours
Text and Reference Books
Text Book
Rosen K.H., Discrete Mathematics and its applications, 5^{th} Edition, McGraw Hill Companies
References
Kolma, Busby, Ross; Discrete Mathematical Structures, Prentice – Hall of India.
 Joshnsonbaugh; Discrete Mathematics, Pearson Education Asia.
Seymour Lipschutz and Marc Lipson; Discrete Mathematics, (Schaum's Outline).
S.M. Maskey: First course in Graph Theory, Published by Ratna Pustak Bhandar.
 G. Gooduire and M. M. Paramenter, Discrete mathematics with graph theory, Prentice – Hall of India.
Narsingh Deo: Graph Theory (with application to engineering and computer science), Prentice
– Hall of India Pvt. Ltd.
 Short Name N/A
 Course code MTH 202
 Semester Second Semester
 Full Marks 100
 Pass Marks 45
 Credit 3 hrs
 Elective/Compulsary Compulsary