Foundations of Computing II
This is a second year (3rd semester) course covering topics from discrete math and formal methods building the foundation of computing. The material of this course is pervasive in the areas of algorithms, data structures and programming but appears virtually in all areas of computer science as well. The course will cover topics such as, but not limited to, proof methods, formal languages, deterministic and nondeterministic finite automata, grammars and pushdown automata, Turing machines, computability, decidability and complexity, P and NP, NP-completeness.
Learning Outcomes
The goal of the course is to familiarize the student with formal methods of computing and their value for computer science and related disciplines, and to provide basic training in applying formal methods to many different kinds of problems. Students should learn the fundamental limits of computation and extend their knowledge on formal languages as well as on formal programming models. Principles of interference, deduction, induction and contradiction should regularly be applied to demonstrate the formal correctness of models and limits.
Course Topics
- Introduction to Computing
- Course Organisation
- Regular Expressions
- Finite Automata
- Equivalence of Models
- Automata Minimisation
- Pumping Lemma, Closure Properties, Algorithms for Regular Languages
- Context-free Grammars
- Chomsky Normal Forms
- Pushdown Automata
- Pumping lemma, closure properties, deterministic pushdown automata
- Syntax Analysis: CYK algorithm, LL1 LR2
- Turing machines
- Undecidability, Reductions
- Further undecidability results (PCP), Rice's theorem
- Universal Turing machine, Semidecidability
- P vs NP
- Cook's theorem
- Further NP-complete problems
- Beyond NP
Classes
There are six classes, every other week starting week 3, and an exam revision at the end of the semester.
- Regular expressions
- Finite Automata
- Pumping lemma for regular languages, Context Free Grammars
- Pushdown automata, pumping lemma, syntax analysis
- Turing machines, undecidability
- NP-completeness