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