CP7201 THEORETICAL FOUNDATIONS OF COMPUTER SCIENCE - ANNA UNIV CSE PG 2ND SEM SYLLABUS

ANNA UNIVERSITY, CHENNAI REGULATIONS - 2013 M.E. COMPUTER SCIENCE AND ENGINEERING CP7201 THEORETICAL FOUNDATIONS OF COMPUTER SCIENCE OBJECTIVES:  To review sets, relations, functions, and other foundations  To understand propositional and predicate logics and their applications  To understand lambda calculus and functional programming  To understand graph structures and their applications  To understand formal models of computation, computability, and decidability UNIT I FOUNDATIONS Sets – relations – equivalence relations – partial orders – functions – recursive functions – sequences – induction principle – structural induction – recursive algorithms – counting – pigeonhole principle – permutations and combinations – recurrence relations UNIT II LOGIC AND LOGIC PROGRAMMING Propositional logic – syntax – interpretations and models – deduction theorems – normal forms – inference rules – SAT solvers - predicate logic – syntax – proof theory – semantics of predicate logic – undecidability of predicate logic – inferences in first-order logic – logic programming – definite programs – SLD resolution – normal programs – SLDNF resolution – introduction to Prolog UNIT III LAMBDA CALCULUS AND FUNCTIONAL PROGRAMMING Lambda notation for functions – syntax – curried functions – parametric polymorphism – lambda reduction – alpha reduction – beta reduction – beta abstraction – extensionality theorem – delta reduction – reduction strategies – normal forms – Church-Rosser Theorems – pure lambda calculus – constants – arithmetic – conditionals – Iteration – recursion – introduction to functional programming UNIT IV GRAPH STRUCTURES Tree Structures – Graph structures – graph representations – regular graph structures – random graphs – Connectivity – Cycles – Graph Coloring – Cliques, Vertex Covers, Independent sets – Spanning Trees – network flows – matching UNIT V STATE MACHINES Languages and Grammars – Finite State Machines – State machines and languages – Turing Machines – Computational Complexity – computability – Decidability – Church's Thesis TOTAL : 45 PERIODS OUTCOMES: Upon Completion of the course,the students will be able  To explain sets, relations, functions  To conduct proofs using induction, pigeonhole principle, and logic  To apply counting, permutations, combinations, and recurrence relations  To apply recursive functions and lambda calculus  To explain logic programming and functional programming principles  To apply sequential structures, tree structures, and graph structures  To explain computational models, computability, and complexity REFERENCES: 1. Uwe Schoning, "Logic for Computer Scientists", Birkhauser, 2008. 2. M. Ben-Ari, "Mathematical logic for computer science", Second Edition, Springer, 2003. 3. John Harrison, "Handbook of Practical Logic and Automated Reasoning", Cambridge University Press, 2009. 4. Greg Michaelson, "An introduction to functional programming through lambda calculus", Dover Publications, 2011. 5. Kenneth Slonneger and Barry Kurtz, "Formal syntax and semantics of programming languages", Addison Wesley, 1995. 6. Kenneth H. Rosen, "Discrete Mathematics and its applications", Seventh Edition, Tata McGraw Hill, 2011. 7. Sriram Pemmaraju and Steven Skiena, "Computational Discrete Mathematics", Cambridge University Press, 2003. 8. M. Huth and M. Ryan, "Logic in Computer Science – Modeling and Reasoning about systems", Second Edition, Cambridge University Press, 2004. 9. Norman L. Biggs, "Discrete Mathematics", Second Edition, Oxford University Press, 2002. 10. Juraj Hromkovic, "Theoretical Computer Science", Springer, 1998. 11. J. E. Hopcroft, Rajeev Motwani, and J. D. Ullman, "Introduction to Automata Theory, Languages, and Computation", Third Edition, Pearson, 2008.

URL: http://feedproxy.google.com/~r/StudentsBlog100/~3/aQa31J_gAh0/cp7201-theoretical-foundations-of-computer-science-pg-cse-2nd-sem-syllabus.html