**M.E COMPUTER SCIENCE AND ENGINEERING**

**REGULATION 2013**

**SEMESTER-II**

**CP7201 THEORETICAL FOUNDATIONS OF COMPUTER SCIENCE**

**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 12

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 12

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

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 12

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 12

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 12**

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 12

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 12

Languages and Grammars – Finite State Machines – State machines and languages – Turing

Machines – Computational Complexity – computability – Decidability – Church's Thesis.

TOTAL : 60 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

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 12

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 12

Languages and Grammars – Finite State Machines – State machines and languages – Turing

Machines – Computational Complexity – computability – Decidability – Church's Thesis.

TOTAL : 60 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.

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.

**EBOOKS:****http://uploading.com/75m584cb/2-M-Ben-Ari-Mathematical-logic-for-computer-science-Second-Edition-Springer-2003-pdf**

**http://www.mediafire.com/download/u1hpsy8n6c91psq/2.M.+Ben-Ari%2C+%E2%80%9CMathematical+logic+for+computer+science%E2%80%9D%2C+Second+Edition%2C+Springer%2C+2003.pdf**

**DOWNLOAD**

Can I get FMSS last yr arrear paper

ReplyDeletecan i get ME CSE 1SEM previous qoestion papers

ReplyDeletei need machine learning CP7009 notes pls

ReplyDeleteSir,i need PG.material in M.E - Computer aided design under anna university..exam is going so,pls rply me soon

ReplyDeletemy email id-samyn21@gmail.com