Discrete Mathematics

Course Objectives :

1.  To introduce the concept of Mathematical Logic, concepts of sets, relation and functions
2.  To introduce the concept of Algorithm and number theory
3.  To understand Group theory and related examples
4.  To use Graph theory for solving problems

Course Outcomes (CO)

• CO1: Ability for constructing mathematical logic to solve problems
• CO2: Ability to Analyze/ quantify the efficiency of a developed solution (algorithm) of a computational problem
• CO3: Ability to Understand mathematical preliminaries to be used in the subsequent courses of the curriculum. This includes Boolean algebra, number theory, group theory, and combinatorics.
• CO4: Ability to Understand diverse relevant topics in discrete mathematics and computation theory with an emphasis on their applicability as mathematical tools in computer science.

UNIT – I

Sets, Logic, and Relation: Sets, Subsets, powerset, operations on sets, Propositional Logic, Rules of inferences in propositional logic, Quantifiers, Predicates and validity, Predicate Logic, normal forms. Proof Techniques Direct Proof, Proof by Contraposition, and proof by contradiction. Principle of inclusion and exclusion, pigeonhole principle, permutation and combination. Principle of Well Ordering, principle of mathematical induction, principle of complete induction. Relation, properties of binary relation, equivalence relation and class, closures (symmetric, reflexive, and transitive).

UNIT – II

Functions, Order relations and Boolean Algebra: Functions, Growth of functions, Permutation functions, Partially ordered sets, lattices, Boolean algebra, Minimization of Boolean Expressions. GCD, LCM, prime numbers.

Recurrence relations, solution methods for linear, first-order recurrence relations with constant coefficients, generating functions, Analysis of Algorithms involving recurrence relations, solution method for a divide-and-conquer recurrence relation. Masters theorem (with proof).

UNIT – III

Group theory: Semi-group, Monoid, Groups, Group identity and uniqueness, inverse and its uniqueness, isomorphism and homomorphism, subgroups, Cosets and Lagrange’s theorem, Permutation group and Cayley’s theorem (without proof), Normal subgroup and quotient groups. Groups and Coding.

UNIT – IV

Graph theory: Graph Terminology, Planar graphs, Euler’s formula (proof), Euler and Hamiltonian path/circuit. Chromatic number of a graph, five color theorem (proof), Shortest path and minimal spanning trees and algorithms, Depth-first and breadth first search, trees associated with DFS & BFS, Connected components. Complexity Analysis of the graph MST.

Textbook(s):

1. 1. B. Kolman, R. C. Busby & S.C. Ross “Discrete Mathematical Structures”, 6th edition, PHI/Pearson, 2009.
2. 2. R. L. Graham, D. E. Knuth & O. Patashnik, “Concrete Mathematics”, Pearson Education, 2000.

References:

1. Neal Koblitz, “A course in number theory and cryptography”, Springer – Verlag, 1994.
2. J.P. Tremblay & R. Manohar, “Discrete Mathematical Structure with Application to Computer Science,” TMH, New Delhi (2000).
3. Norman L. Biggs, “Discrete Mathematics”, Second edition, Oxford University Press, New Delhi (2002).
4. T .H . Cormen, C . E . Leiserson, R .L . Rivest “Introduction to Algorithms”, 3rd edition, PHI/Pearson.
5. Anne Benoit, Yves Robert, Frédéric Vivien “A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis”, CRC Press, 2013.