| Unit name | Theory of Computation |
|---|---|
| Unit code | COMS11700 |
| Credit points | 10 |
| Level of study | C/4 |
| Teaching block(s) |
Teaching Block 2 (weeks 13 - 24) |
| Unit director | . Warinschi |
| Open unit status | Not open |
| Pre-requisites |
EMAT10704 Discrete Mathematics for Computer Scientists COMS11600 Procedural Programming |
| Co-requisites |
None |
| School/department | Department of Computer Science |
| Faculty | Faculty of Engineering |
This unit provides an introducion to various classical models of computation, the equivalence of different computational models, and limits on what can be computed in terms of uncomputability and intractability.
4 CW (20% each), 1 Presentation (20%)
The course text is Introduction to the Theory of Computation, 1st or 2nd edition. The 1st edition is out of print, but still available. All these books are available in the library.
M.Sipser. Introduction to the theory of computation. International Thompson Publishing Company. 1997. ISBN: 053494728X Recommended.
M. Garey and D. Johnson. Computers and intractability: a guide to the theory of NP completeness. W. H. Freeman. 1979. ISBN: 0716710455 Background
J. Truss Discrete mathematics for computer scientists (2nd edition) Addison-Wesley. 1998. ISBN: 0201360616 Background.
