MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

MC9221          MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE   

                                                                                                   L T P C

                                                                                                  3 1 0 4                                                                                                  

UNIT I              Matrix Algebra                                                                                 12

Matrices, Rank of Matrix, Solving System of Equations-Eigen Values and Eigen Vectors-Inverse of a Matrix - Cayley Hamilton Theorem

                                                                       

UNIT II            BASIC SET THEORY                                                                              12 Basic Definitions - Venn Diagrams and set operations - Laws of set theory - Principle of inclusion and exclusion - partitions- Permutation and Combination - Relations- Properties of relations - Matrices of relations - Closure operations on relations - Functions - injective, surjective and bijective functions.

UNIT III           MATHEMATICAL LOGIC                                                                       12

Propositions and logical operators - Truth table - Propositions generated by a set, Equivalence and implication - Basic laws- Some more connectives - Functionally complete set of connectives- Normal forms - Proofs in Propositional calculus - Predicate calculus.

                                   

UNIT IV           FORMAL LANGUAGES                                                                          12

Languages and Grammars-Phrase Structure Grammar-Classification of Grammars-Pumping Lemma For Regular Languages-Context Free Languages.

UNIT V   FINITE STATE AUTOMATA                                                                              12        Finite State Automata-Deterministic Finite State Automata(DFA), Non Deterministic Finite State Automata (NFA)-Equivalence of DFA and NFA-Equivalence of NFA and Regular Languages.                 

                                                                                                Total No. of  Periods: 60

REFERENCES

1.   Kenneth H.Rosen, “ Discrete Mathematics and Its Applications”, Tata McGraw Hill,

     Fourth Edition, 2002 (Unit 1,2 & 3).

1.   Hopcroft and Ullman, “Introduction to Automata Theory, Languages and Computation”, Narosa Publishing House, Delhi, 2002. ( Unit 4,5)

2. A.Tamilarasi & A.M.Natarajan, “Discrete Mathematics and its Application”, Khanna

                  Publishers, 2^nd Edition 2005.

            4.   M.K.Venkataraman “Engineering Mathematics”, Volume II, National Publishing

      Company, 2^nd Edition,1989.