| Course Code: CS205M Course Name: Theoretical Foundations of Computer Science Prerequisites: NIL Syllabus: Functions, relations, partial orders, recurrences, summations, generating functions, asymptotics Graphs: basic concepts Elementary Logic and proof techniques. Alphabets, Languages, Grammars Finite automata: regular expressions, regular languages Context free languages: pushdown automata Turing machines: recursively enumerable languages Chomsky hierarchy. Texts: 1. K. H. Rosen, Discrete Mathematics and its Applications., McGraw Hill International Edition, 1999. 2. J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Pearson Education, 3rd Edition, 2007. References: 1. J. P. Tremblay, P. R. Manohar, Discrete Mathematics with Applications to Computer Science, McGraw Hill International Edition, 1989. 2. C. L. Liu, Elements of Discrete Mathematics. 2/e. McGraw-Hill International Edition, 1986. 3. M. Sipser, Introduction to the Theory of Computation, Thomson, 1997.4. H. R. Lewis, C. H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall of India, New Jersey, 1981. |