Outline:
1. Sets - Relations - Posets - Functions - Mathematical Inductions (Simple and strong) - Propositional and Predicate Calculus - Proof by inference and truth tables.
2. Graphs - Basic concepts - Connectedness - Isomorphism – complements - Matrix representation of graphs - Adjacency and Incidence Matrices – Trees.
3. Spanning trees, Euler and Hamiltonian graphs - directed graphs - Strong connectedness graphs - MST algorithms of Prim and Kruskal - Shortest path and Max-flow algorithms.
4. Groups, subgroups, normal subgroups, Vector spaces, Basis and Dimension, Linear codes, Error Correction, generating Matrix, Standard decoding table, perfect and quasi-perfect codes.
5. Regular Grammars – Finite Automata – Context-Free Grammars – Chomsky’s Normal form -Griebach Normal Form - Push-down Automata - Equivalence of CFL’s and PDA’s - Non-context free languages.
Books:
1. Arthur Gill, "Applied Algebra for Computer Science", 1976, PHI
2. Narsingh Deo, "Graph theory and application to Engineering and computer Science", 1986, PHI
3. Gyorgy E. Revesz, "Introduction to Formal Languages" Mc-Graw Hill, 1986
