Sets - Relations – Posets - Functions - Mathematical Inductions (Simple and strong) – Principles of Counting (Addition & Multiplication)
Graphs - Basic concepts - Isomorphism – complements - Matrix representation of graphs - Trees, Spanning trees, Minimal Spanning tree Algorithms - Euler graphs - Hamiltonian graphs.
Recurrence Relations and Generating Functions - Homogeneous and non-homogeneous recurrences and their solutions - solving recurrences using generating functions
Mathematical Logic – Predicate Calculus – Scope – Binding – Resolution – 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
REFERENCES:
1. Thomas Koshy, “Discrete Mathematics with Applications”, Elsevier,2006.
2. NarsinghDeo, “Graph theory and applications to Engineering and Computer Science”, PHI,1986.
3. Arthur Gill, “Applied Algebra for the Computer Sciences”, Prentice Hall,1976.
4. Michael Sipser, “Introduction to Theory of Computation”, PWS Publishing Co,1996.
COURSE OUTCOME:
Students will be able to
1.Explain functions and related concepts and illustrate its direct application in Computer languages
2. Solve the problems using the concepts of Graphs, Trees.
3. Deduce complex task by various Mathematical logic.
4. Solve recurrence relations for a given problem.
