Intelligent Systems Group

Alan Frisch's Teaching Pages:
Theory of Computation (TOC)

Announcements

• The TOC resit exam given during the 1998 summer break will be an unseen 90 minute paper (worth 50 marks): answer 2 questions (25 marks each) from 3. The examination contains one question based predominantly on each component of the module.

General Information

• Module Information
• Syllabus
• Practical Groups

Unit 1: Logic

• This unit builds directly upon material taught in the Introduction to Computer Mathematics (ICM) module.
• Lecture Notes: Introduction to Logic
• Lecture Notes: Propositional Logic
• Lecture Notes: First-Order Predicate Calculus

Unit 2: Computability

• This unit builds directly upon the material taught in the "Formal Languages and Automata" Unit of the Mathematics for Computer Science (MCS) module.
• A Review of Formal Languages and Grammars
  This covers the basic material on languages and grammars from MCS and TOC.

Unit 3: NP-Completeness

• This unit builds directly upon material taught in the Algorithms and Data Structures (ADS) module.

Practicals

• Week 1 Practicals: Problems and Solutions
• Week 2 Practicals: Problems and Solutions
• Week 3 Practicals: Problems and Solutions
• Week 4 Practicals: Problems and Solutions
• Week 5 Practicals: Problems and Solutions
• Week 6 Practicals: Problems and Solutions
• Week 7 Practicals: Problems and Solutions

Practice Exam

• Practice Exam 1: Problems and Solutions

Past Exams

• Exam from 94/95
• Exam from 95/96
• Exam from 96/97
• Exam from 97/98

Future Exams

• Exam for 98/99

Alan Frisch's Home Page