Introduction to Theoretical Computer Science - examinable material

In general, you should know what was on the slides, and you should recognize anything that was on coursework or tutorial exercises.

The following list goes through the course, summarizing the things you should know (i.e. memorize), and the things you should be able to do if asked in a question.

NOTE: Mastery of the following should ensure an A3 grade in the exam. However, the University Marking Scheme requires that A2 and A1 grades should be used for students who have gone beyond, and well beyond, the expectations of the course. Exams may, therefore, make some use of material that is only mentioned in passing, in the notes, or in additional reading. Such material will usually be confined to the final subpart of a question.

Things to knowThings to do
Register machine definition Write short programs for RMs
Argue for the Church-Turing thesis
concepts of Pairing functions and coding functions design a coding function for some datatype
simulate one machine by another
the Halting Theorem prove the theorem
Turing machine definition sketch TM programs
argue the equivalence of TMs and RMs
defn of computable function
defn of (decidable) decision problem
defn of many-one reduction
reduction from undecidable problem shows undecidability prove the theorem; use the theorem on simple examples
Uniform Halting prove undecidable
defn of (co-)semi-decidable
preservation of (co-)semi-decidability by m-reductions prove this
defn of computably enumerable show that H and similar problems are c.e.
Looping Problem prove L is co-semi-decidable
semi-dec and co-semi-dec => dec prove this; prove L is not semi-decidable
preservation of (co-)semi-decidability by reductions prove UH or similar problems not (co)-semi-decidable
big/little O and omega notation simple analyses
definition of P show that algorithms/problems are in P
argue for/against P as a good defn of tractable
defn of PTime-reduction
defn of P-bounded machines; redefn of P using these
defn of non-deterministic machines write simple programs
show that NRMs compute same functions as RMs
defn of NP by PTime-bounded RMs
guess-and-check defn; equivalence thereof show problems in NP by guess-and-check
defn of NP-hard/complete
preservation of NP-hard by reduction prove this; use it in simple examples
HPP, Timetabling as NP-complete
defn of SAT
Cook-Levin Theorem prove in outline
defn of 3SAT reduce from 3SAT to other problem
defn of CLIQUE reduce from CLIQUE to similar problems
NP-hardness of CLIQUE by redn from 3SAT
ExpTime believed strictly bigger than NP
lambda-calculus syntax write simple lambda-expressions
alpha,beta,eta-conversion do these
call-by-name and call-by-value reduction strategies use these
simple extensions: if, arithmetic
concept of recursion use Y operator if given
simple types
typing rules write types for lambda-expressions
write a formal derivation tree for the type of an expressoin
properties of simple types (slide 85)
fix typing rule write simple recursive functions with fix
general scheme for extending language write typing and evaluation rules for a new extension
defns of let and letrec as syntactic sugar use these
concept of type inference infer types `by hand'
outline of type inference using variables do inferences in outline
type schemes/polytypes as quantified variable types give polytypes `by hand'
let(rec) as primitives
Hindley-Milner algorithm in outline

Home : Teaching : Courses : Itcs 

Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail:
Please contact our webadmin with any comments or corrections. Logging and Cookies
Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh