Unit information: Topics in Theoretical Computer Science in 2012/13

Please note: you are viewing unit and programme information for a past academic year. Please see the current academic year for up to date information.

Unit name Topics in Theoretical Computer Science
Unit code COMS21400
Credit points 10
Level of study I/5
Teaching block(s) Teaching Block 1 (weeks 1 - 12)
Unit director Dr. Ray
Open unit status Not open
Pre-requisites

COMS11700 Theory of Computation COMS11600 Principles of Programming

Co-requisites

None
School/department Department of Computer Science
Faculty Faculty of Engineering

Description including Unit Aims

This unit covers two core areas of theoretical computer science: semantics and complexity theory. Semantics provide a means to attach precise meaning to a computer program, which in turn allows reasoning about correctness and feasibility (what programs make sense). Complexity theory looks at feasibility from a different perspective, emphasizing the problems (for which problems do we or don't we expect efficient solutions).

Intended Learning Outcomes

On successful completion of this unit you will be able to:

  • Give a more precise definition of what a computer program means.
  • Prove correctness of simple programs.
  • Know the difference between axiomatic, operational, and denotational semantics.
  • Apply semantics to various programming paradigms.
  • Identify the main complexity classes.
  • Provide some polynomial-time reductions.
  • Understand that there are different ways of measuring complexity.
  • Appreciate the use of randomized algorithms.

Teaching Information

Lectures and problem classes

Assessment Information

Coursework (20%) and a three-hour examination (80%) The examination will consist of a series of questions, that combined will cover all the learning objectives.

The coursework will consist of a series of questions, the answers of which the students can work on in their own time (unsupervised). It will cover a selection of the learning objectives, depending on the order they are being taught, and have a diagnostic and formative element to it.

Reading and References

  • H.R. Nielson and F. Nielson (1999). Semantics with Applications: A

Formal Introduction, originally published in 1992 by John Wiley and Sons, revised edition: http://www.doc.ic.ac.uk/~pg/Computation/book.pdf

  • G. Winskel (1993). The Formal Semantics of Programming Languages, MIT

Press. This is an excellent introduction to both the operational and denotational semantics of programming languages.

  • Michael Sipser (2006). Introduction to the Theory of Computation.

Related links