CP7201 THEORETICAL FOUNDATIONS OF COMPUTER SCIENCE

CP7201     THEORETICAL FOUNDATIONS OF COMPUTER SCIENCE

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 – Davis Putnam procedure – binary decision diagrams – predicate logic – syntax – proof theory – semantics of predicate logic – undecidability of predicate logic - Normal form – unification –  - 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.  

  

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.