The descriptions are for modules currently being taught. They should be viewed as an example of the modules we provide. All modules are subject to change for later academic years.

Computability & Complexity (COCO) 2015/6

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

Module Prerequisites

Prerequisite knowledge

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

Prerequisite modules

Workload

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

Private Study

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.

Assessment

Closed Assessment

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

Formative Feedback

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
and after the tests model answers are provided.

Description

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

Aims

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

Learning Outcomes

  • 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

Content

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

Teaching Materials

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

Recommended Books

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
Back to top

Last updated: 19th September 2016