# COSC341

## Lecture notes/Course Materials 2019

• Each week the lecture and tutorial material will appear online.
• Once the tutorial has been held, sample solutions will be posted.
• Lectures and tutorial solutions from the first half of the semester (lectures 1-13) can also be accessed here.

 Lectures Lecture 1: Introduction Lecture 2: Sets, Relations, Functions Lecture 3: Cardinality Lecture 4: Finite state automata Lecture 5: Non-deterministic automata Lecture 6: NFA=DFA Lecture 7: Pumping Lemma Lecture 8: Pushdown automata and context free grammars Lecture 9: Regular languages Lecture 10: Classification of languages, Pumping Lemma 2 Lecture 11-13: Turing machines Lecture 14: Performance and Complexity 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 Yawen's additional teaching slides can be viewed Here. Tutorials Tutorial 1: Sets and functions | Solutions Tutorial 2: Equivalence relations | Solutions Tutorial 3: Cardinality | Solutions Tutorial 4: Automata | Solutions Tutorial 5: Deterministic and non-deterministic automata | Solutions Tutorial 6: NFA=DFA | Solutions Tutorial 7: Pumping Lemma | Solutions Tutorial 8+9: More Pumping Lemma Tutorial 10: Pushdown automata and context free grammars Tutorial 11: Regular Languages, Pumping Lemma 2Tutorial 14: SolutionsTutorial 15: SolutionsTutorial 16: SolutionsTutorial 17: SolutionsTutorial 18: SolutionsTutorial 19: SolutionsTutorial 20: SolutionsTutorial 21: SolutionsTutorial 22: SolutionsTutorial 23: SolutionsTutorial 24: Solutions

Page maintained by Robert                     Last updated:  23rd May 2019   04:15