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.

Theory of Computing (TOC) 2010/1

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

Module Code 0620132
Lecturers Detlef Plump
Taken By CS 2, CS/Math 2, MMath 2, CSESE 2, MEng CSESE 2, CSSE 2, MEng CSSE 2, MEng CSAI 2
Number of Credits 10
Part A
Teaching Aut/2-7
Closed Assessment [100%] Spring Week 1, 1.50 hours

Module Prerequisites

Prerequisite knowledge

Students entering this module should be comfortable with using the following concepts (taught in ICM, MCS and TAD): sets and relations; functions; mathematical proofs (in particular induction proofs); finite automata; regular expressions; regular grammars; context-free grammars; derivations and languages; notation for function growth. Those whose understanding of this prerequisite material is deficient will need to invest extra time in private study beyond that listed in the workload section.

Prerequisite modules

Workload

  • Lectures: 18 x 1hr
  • Practicals: 6 x 2hrs
  • Private Study: 68.5hrs
  • Assessment: 1.5hrs

Practical classes are with tuition. Important: Working individually through exercises - in addition to the group work in practical classes - is essential for understanding the material.

Students should be aware that the module is taught in a "compressed format", running six weeks only. Hence the weekly workload is higher than normal for a 10-credit module: it comprises three hours of lectures, two hours of practicals, and 8.5 hours of private study (see below).

Private Study

"Private study" comprises 33 hours unsupervised work on exercises, 18 hours reviewing lectures and reading textbooks, and 17.5 hours preparing for the closed exam. Because the module runs only six weeks, the weekly load amounts to 5.5 hours unsupervised work on exercises and 3 hours reviewing lectures and reading textbooks (not including the preparation for the exam).

Assessment

Closed Assessment

  • Spring Week 1, 1.50 hours

An unseen paper worth 50 marks. Candidates are required to answer any two questions from three.

Formative Feedback

Practicals consist of group work on weekly exercises. Group solutions to exercises are handed in, marked by demonstrators and returned. In addition, groups and individual students get oral feedback by demonstrators and the lecturer during practicals.

Description

Building upon the foundations laid in the first year, this module introduces students to three areas of theoretical computer science: formal languages (continuing the introduction of the first year), computability theory, and complexity theory.

Learning Outcomes

Students will obtain a basic understanding of specifications and properties of formal languages, classes of solvable and unsolvable problems, and classes of tractable and untractable problems. In addition, the students' ability to think and communicate with rigour will be improved.

Content

The module comprises three parts.

  1. Formal languages: brief review of regular and context-free languages from first year; context-sensitive languages (context-sensitive grammars and linear-bounded automata); type-0 languages (unrestricted grammars and Turing machines); the Chomsky hierarchy.
  2. Computability theory: decidable and semidecidable languages; Turing-computable functions; decidable and undecidable problems; Church's thesis.
  3. 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 will be available from 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
*
* Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D. Introduction to Automata Theory, Languages and Computation (3rd ed.) Pearson Education 2007
* Lewis, Harry R. and Papadimitriou, Christos H. Elements of the Theory of Computation (2nd ed.) Prentice-Hall 1998
* Sipser, Michael Introduction to the Theory of Computation (2nd ed.) Course Technology Inc 2005
* Sudkamp, Thomas A. Languages and Machines (3rd ed.) Pearson Education 2006
* Wegener, Ingo Complexity Theory Springer-Verlag 2005
* Rich, Elaine Automata, Computability and Complexity Pearson Education 2008
++ 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: 1st June 2011