COSC341

Theory of Computing

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 2
Tutorial 14: Solutions
Tutorial 15: Solutions
Tutorial 16: Solutions
Tutorial 17: Solutions
Tutorial 18: Solutions
Tutorial 19: Solutions
Tutorial 20: Solutions
Tutorial 21: Solutions
Tutorial 22: Solutions
Tutorial 23: Solutions
Tutorial 24: Solutions




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