prepare for your B.Tech Mathematical Foundation of Computer Science 2020 edition examinations. Referring to the connections we’ve provided below and the links containing the study materials in PDF format, and the list of recommended books that we’ve provided below, you will be able to ace your examinations. We have also provided you with further details that will allow you to do well in your exams and learn more. These study materials help you understand the concepts and everything quickly and creates a better space for you to work on. These study materials give you the best resources to study from.

## Download Study Materials

MFCS lecture notes | Download |

MFCS Notes ppt | Download |

Mathematical Foundation of Computer Science Question Paper | Download |

Mathematical Foundation of Computer Science Study Material | Download |

## Recommended Books

- Discrete Mathematical Structures with Applications to Computer Science, J. P.Tremblay and P. Manohar, Tata McGraw Hill.
- Elements of Discrete Mathematics-A Computer Oriented Approach, C. L. Liu and D. P. Mohapatra, 3rdEdition, Tata McGraw Hill.
- Discrete Mathematics and its Applications with Combinatorics and Graph Theory, K. H. Rosen, 7th Edition, Tata McGraw Hill.
- Discrete Mathematics for Computer Scientists and Mathematicians, J. L. Mott, A. Kandel, T.P. Baker, 2nd Edition, Prentice Hall of India.
- Discrete Mathematical Structures, BernandKolman, Robert C. Busby, Sharon Cutler Ross, PHI.
- Discrete Mathematics, S. K. Chakraborty and B.K. Sarkar, Oxford, 2011.

## Syllabus

UNIT -I: Mathematical Logic:

Propositional Calculus: Statements and Notations, Connectives, Well-Formed Formulas, Truth Tables, Tautologies, Equivalence of Formulas, Duality Law, Tautological Implications, Normal Forms, Theory of Inference for Statement Calculus, Consistency of Premises, Indirect Method of Proof. Predicate Calculus: Predicative Logic, Statement Functions, Variables and Quantifiers, Free and Bound Variables, Inference Theory for Predicate Calculus.

UNIT -II: Set Theory:

Introduction, Operations on Binary Sets, Principle of Inclusion and Exclusion, Relations: Properties of Binary Relations, Relation Matrix and Digraph, Operations on Relations, Partition and Covering, Transitive Closure, Equivalence, Compatibility and Partial Ordering Relations, Hasse Diagrams, Functions: Bijective Functions, Composition of Functions, Inverse Functions, Permutation Functions, Recursive Functions, Lattice and its Properties.

UNIT- III: Algebraic Structures and Number Theory:

Algebraic Structures: Algebraic Systems, Examples, General Properties, Semi Groups and Monoids, Homomorphism of Semi Groups and Monoids, Group, Subgroup, Abelian Group, Homomorphism, Isomorphism, Number Theory: Properties of Integers, Division Theorem, The Greatest Common Divisor, Euclidean Algorithm, Least Common Multiple, Testing for Prime Numbers, The Fundamental Theorem of Arithmetic, Modular

Arithmetic (Fermat‘s Theorem and Euler‘s Theorem)

UNIT -IV: Combinatorics:

Basic of Counting, Permutations, Permutations with Repetitions, Circular Permutations, Restricted Permutations, Combinations, Restricted Combinations, Generating Functions of Permutations and Combinations, Binomial and Multinomial Coefficients, Binomial and Multinomial Theorems, The Principles of Inclusion Exclusion, Pigeonhole Principle and its Application.

UNIT -V: Recurrence Relations:

Generating Functions, Function of Sequences, Partial Fractions, Calculating Coefficient of Generating Functions, Recurrence Relations, Formulation as Recurrence Relations, Solving Recurrence Relations by Substitution and Generating Functions, Method of Characteristic Roots, Solving Inhomogeneous Recurrence Relations

UNIT -VI: Graph Theory:

Basic Concepts of Graphs, Sub graphs, Matrix Representation of Graphs: Adjacency Matrices, Incidence Matrices, Isomorphic Graphs, Paths and Circuits, Eulerian and Hamiltonian Graphs, Multigraphs, Planar Graphs, Euler‘s Formula, Graph Colouring and Covering, Chromatic Number, Spanning Trees, Algorithms for Spanning Trees (Problems Only and Theorems without Proofs).

## Important Questions

- Explain in brief about fermats theorem?
- State Division algorithm and apply it for a dividend of 170 and divisor of 11.
- Explain in brief about the Division theorem?
- Explain in brief about GCD with example?
- Prove that the sum of two odd integers is an even integer?
- Explain in brief about Euler’s theorem with examples?
- Explain in brief about the Principle of Mathematical Induction with examples?
- Define the Prime number? Explain in brief about the procedure for testing of prime numbers?
- Using Fermat’s theorem, find 3201 mod 11.
- Use Euler’s theorem to find a number between 0 and 9 such that a is congruent to 7 1000 (mod 10)
- Prove that a group consisting of three elements is an abelian group?
- Prove that G={-1,1,i,-i} is an abelian group under multiplication?
- Let G= {-1,0,1} . Verify that G forms an abelian group under addition?
- Prove that the Cancellation laws hold good in a group G.?
- Prove that the order of a-1 is the same as the order of a.?
- Find the integers x such that i) 5x≡4 (mod 3) ii) 7x≡6 (mod 5) iii) 9x≡8 (mod 7)
- Determine GCD (1970, 1066) using the Euclidean algorithm.
- If a=1820 and b=231, find GCD (a, b). Express GCD as a linear combination of a and b.
- Find 117 mod 13 using modular arithmetic.