Notes
Slides for the lectures: slides.ps.gzSuggested ExercisesCorrections to the notes handed out at the beginning of the course are given in the errata sheet, last updated on 17 May, 2000.The extra slides used on 12 May on the Circuit Value Problem, are here.
Exercise Sheet 1 (4 May 2000)Past Exam QuestionsErratum: In Question 2 of sheet 1, in order to show that f(g) is constructible, you need to assume that f(n) > n.Exercise Sheet 2 (9 May 2000)
Exercise Sheet 3 (15 May 2000)
Erratum: In Question 3 of sheet 3, the definition of a Horn clause should require at most one positive literal per clause, rather than exactly one.Exercise Sheet 4 (22 May 2000)
Errata: In Question 2 of sheet 4, for "exactly one triple", read "exactly one quadruple".In Question 4, part (b), for "reducible" read "linear time reducible".
As the syllabus for the course has changed this year from what it was in earlier years, some questions from previous exams may not be relevant. However, if you have mastered the material taught this year, you should be able to attempt the following questions from past exams:
- 1993 Paper 5 Question 11
- 1994 Paper 13 Question 10
- 1996 Paper 5 Question 11
- 1997 Paper 5 Question 9
- 1998 Paper 5 Question 11
- 1998 Paper 6 Question 11
- 1999 Paper 6 Question 11