MA5133 – MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENC Sylllabus

ANNA UNIVERSITY TIRUCHIRAPPALLI
Tiruchirappalli - 620 024 Regulations 2007
Sylllabus M.E. COMPUTER SCIENCE AND ENGINEERING
SEMESTER I

MA5133 – MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE


UNIT I FUNDAMENTAL STRUCTURES 9
Set Theory – Relationships between Sets – Operations on Sets – Set Identities – Principle of
Inclusion and Exclusion – Minsets – Relations – Binary Relations – Partial Orderings – Equivalence
Relations – Functions – Properties of Functions – Composition of Functions – Inverse Functions –
Permutation Functions.

UNIT II LOGIC 9
Propositional Logic – Logical Connectives – Truth Tables – Normal Forms (conjunctive and
disjunctive) – Predicate logic – Universal and Existential Quantifiers – Proof Techniques – Direct
and Indirect – Proof by Contradiction – Mathematical Induction.

UNIT III COMBINATORICS 9
Basics of Counting – Counting Arguments – Pigeonhole Principle – Permutations and Combinations
– Recursion and Recurrence Relations – Generating Functions.

UNIT IV MODELING COMPUTATION AND LANGUAGES 9
Finite State Machines – Deterministic and Non– Deterministic Finite State Machines – Turing
Machines – Formal Languages – Classes of Grammars – Type 0 – Context Sensitive – Context –
Free – Regular Grammars – Ambiguity

UNIT.V DISCRETE 9
Finite Probability – Probability Distributions – Conditional Probability – Independence – Bayes’
Theorem – Mathematical Expectation.

L: 45 T: 15 Total: 60

TEXTBOOK
1. Judith L. Gersting, “Mathematical Structures for Computer Science”, 5thEdition, W.H.
Freeman and Company, 2003.

REFERENCES
1. J. P. Tremblay and R. Manohar, “Discrete Mathematical Structures with Applications to
Computer Science”, TMH, 1997.
2. Kenneth H. Rosen, “Discrete Mathematics and its Applications”, 5th Edition, TMH, 2003.
3. R.P. Grimaldi, “Discrete and Combinatorial Mathematics”, Pearson Edition, 2002.
4. M.K. Venkataraman, N. Sridharan and N. Chandrasekaran, “Discrete Mathematics”, The
National Publishing Company, 2003.