- Each week the lecture material will appear online.
- Once the tutorial has been held, sample solutions will be posted.

Lectures |

Lecture 1: Preliminaries |

Lecture 2: Equivalence relations and cardinality |

Lecture 3: Recursion and induction |

Lecture 4: Three types of computing machine |

Lecture 5: Finite state automata and regular languages |

Lecture 6: Non Determinism |

Lecture 7: Regular Languages |

Lecture 8: Not Regular languages |

Lectures 9: Pushdown automata |

Lectures 10-14: Turing machines |

Lecture 15: NP-hard and NP-complete |

Lecture 16: Cook's Theorem (1) |

Lecture 17: Cook's Theorem (2) |

Lecture 18: Additional Complexity Classes |

Lecture 19: Beyond 3-SAT |

Lecture 20: Graph Theoretic NP-complete Problems |

Lecture 21: SUBSET-SUM Problem |

Lecture 22: Optimisation Problems |

Lecture 23: Approximation (1) |

Lecture 24: Approximation (2) |

Lecture 25: Presentations of other hard problems |

Lecture 26: Review and exam Guide |

Tutorials |

Tutorial 1: Solutions |

Tutorial 2: Solutions |

Tutorial 3: Solutions |

Tutorial 4: Tutorial 5: Tutorial 6: Tutorial 7: Tutorial 8+9: Tutorial 10: |

Tutorial 11: Tutorial 14: Tutorial 15: Tutorial 16: Tutorial 17: Tutorial 18: Tutorial 19: Tutorial 20: Tutorial 21: Tutorial 22: Tutorial 23: Tutorial 24: |

Page maintained by Robert
Last updated: 23rd Mar 2020 01:33