Workload - Private Study - Assessment - Description - Aims - Learning Outcomes - Content - Teaching Materials - Recommended Books

Module Code | COM00002I |
---|---|

Lecturers | Detlef Plump, James Cussens |

Taken By | CS 2, CS/Math 2, CS/Phil 2, CSESE 2, CSYS 2, MEng CS 2, MEng CS/Phil 2, MEng CSAI 2, MEng CSESE 2, MEng CSSE 2, MEng CSYS 2, MMath 2 |

Number of Credits | 10 |

Teaching | Spring 2-10 |

Closed Assessment | [100%] Summer 5-7, 1.50 hours |

Reassessment |
[100%]
Closed Exam - August Resit Week, 1.50 hours |

Students should be comfortable with using the following concepts (taught in MFCS and TPOP): sets and relations; functions; finite automata; regular expressions; regular grammars; context-free grammars; derivations and languages; notation for function growth; mathematical proofs (in particular induction proofs).

- Lectures: 15 x 1hr
- Problem Classes: 6 x 2hrs
- Private Study: 70.5hrs
- Assessment: 1 x 1.5hrs
- Formative Tests: 2 x 0.5hrs

Working individually through exercises, in addition to group work during classes, is essential for understanding the material.

Expect to spend a couple of hours each week reviewing your lecture notes and studying textbooks. Another two or three hours may be needed to complete solutions to problem sheets on which work has been started in classes. The remaining private-study time is for revision.

- Summer 5-7, 1.50 hours

After the exam, summary feedback is provided for the whole class. Students also have supervised access to their marked exam scripts.

Problem classes are used for working in groups on exercises. Groups and individual students get oral feedback by teaching assistants and the lecturer during problem classes. Model solutions are provided online for comparison.

There are two formative tests in

- Spring Week 6
- Spring Week 9

Building upon the foundations laid in the first year, this module introduces basic concepts and results in computability theory and complexity theory.

The aim of this module is to introduce basic concepts and results in computability theory and complexity theory.

- Understanding of Turing-recognizable languages, Turing-computable functions, and the difference between solvable and unsolvable problems
- Ability to prove unsolvability by reduction
- Understanding the time and space complexity of Turing machines, the complexity classes P and NP, and NP-completeness
- Ability to prove NP-completeness by reduction

- Beyond context-free languages: context-sensitive and unrestricted grammars; Turing machines; the Chomsky hierarchy.
- Computability theory: decidable and semidecidable languages; Turing-computable functions; decidable and undecidable problems; Church's thesis.
- Complexity theory: time and space complexity of Turing machines; the complexity classes P and NP; reducibility, NP-hardness and NP-completeness; examples of NP-complete problems.

Lecture slides and exercises (with solutions in due course) are available on the module web page.

Rating | Author | Title | Publisher | Year |
---|---|---|---|---|

**** | Martin, John C. | Introduction to Languages and the Theory of Computation (4th ed.) | McGraw Hill | 2010 |

** | Rich, Elaine | Automata, Computability and Complexity | Pearson Education | 2008 |

** | Sipser, Michael | Introduction to the Theory of Computation (3rd ed.) | South-Western College Publishing | 2012 |

* | Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D. | Introduction to Automata Theory, Languages and Computation (3rd ed.) | Pearson Education | 2013 |

* | Arora, Sanjeev and Barak, Boaz | Computational Complexity: A Modern Approach | Cambridge University Press | 2009 |

++ | Garey, Michael R. and Johnson, David S. | Computers and Intractability: A Guide to the Theory of NP-Completeness | W.H. Freeman | 1979 |

Last updated: 19^{th} September 2016