JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD 

II Year B.Tech. CSE - I Sem L T/P/D C

4 -/-/-  4 

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 

---

Objectives:

• To explain with examples the basic terminology of functions, relations, and sets.
• To perform the operations associated with sets, functions, and relations.
• To relate practical examples to the appropriate set, function, or relation, or relation model, and interpet the associated operations and terminology in context.
• To describe the  importance and limitations of predicate logic.
• To relate the ideas of mathematical introduction to recursion and recursively defined structures.
• To use Graph Theory for solving problems.

UNIT- I 

Mathematical Logic : Statements and notations, Connectives, Well formed formulas, Truth Tables, tautology, equivalence implication, Normal forms, Quantifiers, Universal quantifiers.Predicates : Predicative logic, Free & Bound variables, Rules of inference, Consistency, proof of contradiction, Automatic Theorem Proving. 

UNIT- II 

Relations: Properties of Binary Relations, equivalence, transitive closure, compatibility and partial ordering relations, Lattices, Hasse diagram. Functions: Inverse Function Composition of functions, recursive Functions, Lattice and its Properties, Algebraic stuctures: Algebraic systems Examples and general properties, Semi groups and monads, group sub groups homomorphism, Isomorphism.

UNIT- III 

Elementary Combinatorics: Basis of counting, Combinations & Permutations, with repetitions, Constrained repetitions, Binomial Coefficients, Binomial Multinomial theorems, the principles of Inclusion – Exclusion. Pigeon hole principles and its application. 

UNIT- IV

Recurrence Relation : Generating Functions, Function of Sequences Calculating Coefficient of generating function, Recurrence relations, Solving recurrence relation by substitution and Generating funds. Characteristics roots solution of In homogeneous Recurrence Relation. 

UNIT- V 

Graph Theory: Representation of Graph, DFS, BFS, Spanning Trees, planar Graphs. Graph Theory and Applications, Basic Concepts Isomorphism and Sub graphs, Multi graphs and Euler circuits, Hamiltonian graphs, Chromatic Numbers.

 TEXT BOOKS : 

1. Elements of DISCRETE MATHEMATICS - A computer Oriented Approach - C L Liu, D P Mohapatra. Third Edition, Tata McGraw Hill.
2. Discrete Mathematics for Computer Scientists & Mathematicians, J. L. Mott, A. Kandel, T.P. Baker PHI.

REFERENCES : 

1. Discrete Mathematics with Applications, Thomas Koshy, Elsevier.
2. Discrete Mathematical structures Theory and application-Malik & Sen, Cengage. 
3. Discrete Mathematics and it's Applications, Kenneth H. Rosen, Fifth Edition. TMH.
4. Logic and Discrete Mathematics, Grass Man & Trembley, Person Education.

Outcomes:

• Ability to Illustrate by examples the basic terminology of functions, relations, and sets and demonstrate knowledge of their associated operations.
• Ability to Demonstrate in practical applications the use of basic counting principles of permutations, combinations, inclusion/exclusion princple and the pigeonhole methodology.
• Ability to represent and Apply theory in solving computer science problems.

Note: This syllabus is same for CSE, IT/CST.