CS303ES: MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE
B.Tech. II Year I Sem. L T P C
4 0 0 4

---

Course Objectives:

• To introduce the concepts of mathematical logic.
• To introduce the concepts of sets, relations, and functions.
• To perform the operations associated with sets, functions, and relations.
• To relate practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context.
• To introduce generating functions and recurrence relations.
• To use Graph Theory for solving problems.

Course Outcomes

• Ability to apply mathematical logic to solve problems.
• Understand sets, relations, functions, and discrete structures.
• Able to use logical notation to define and reason about fundamental mathematical concepts such as sets, relations, and functions.
• Able to formulate problems and solve recurrence relations.
• Able to model and solve real-world problems using graphs and trees.

UNIT - I

Mathematical logic: Introduction, Statements and Notation, Connectives, Normal Forms, Theory of Inference for the Statement Calculus, The Predicate Calculus, Inference Theory of the Predicate Calculus.

UNIT - II

Set theory: Introduction, Basic Concepts of Set Theory, Representation of Discrete Structures, Relations and Ordering, Functions.

Algebraic Structures: Introduction, Algebraic Systems, Semi groups and Monoids, Groups, Lattices as Partially Ordered Sets, Boolean algebra.

UNIT - III

Elementary Combinatorics: Basics of Counting, Combinations and Permutations, Enumeration of Combinations and Permutations, Enumerating Combinations and Permutations with Repetitions, Enumerating Permutations with Constrained Repetitions, Binomial Coefficients, The Binomial and Multinomial Theorems, The Principle of Inclusion- Exclusion.

UNIT - IV

Recurrence Relations: Generating Functions of Sequences, Calculating Coefficients of generating functions, Recurrence relations, Solving recurrence relations by substitution and Generating functions, The method of Characteristic roots, Solutions of Inhomogeneous Recurrence Relations.

UNIT - V

Graphs: Basic Concepts, Isomorphisms and Subgraphs, Trees and their Properties, Spanning Trees, Directed Trees, Binary Trees, Planar Graphs, Euler’s Formula, Multigraphs and Euler Circuits, Hamiltonian Graphs, Chromatic Numbers, The Four-Color Problem.

TEXT BOOKS:

1. Discrete Mathematical Structures with Applications to Computer Science, J.P. Tremblay, R. Manohar, McGraw Hill education (India) Private Limited. (UNITS - I, II)
2. Discrete Mathematics for Computer Scientists & Mathematicians, Joe L. Mott, Abraham Kandel, Theodore P. Baker, Pearson , 2nd ed. (Units - III, IV, V)

REFERENCE BOOKS:

1. Discrete Mathematics and its Applications, Kenneth H. Rosen, 7th Edition, McGraw Hill education (India) Private Limited.
2. Discrete Mathematics, D.S. Malik & M.K. Sen, Revised edition Cengage Learning.
3. Elements of Discrete Mathematics, C. L. Liu and D. P. Mohapatra, 4th edition, McGraw Hill education (India) Private Limited.
4. Discrete Mathematics with Applications, Thomas Koshy, Elsevier.
5. Discrete and Combinatorial Mathematics, R. P. Grimaldi, Pearson.