2019 Theory of Computing

Alex and Lena are involved in teaching COSC341 Theory of Computing.

Complete set of lectures (first half of the semester) is being continuously updated and will be finalised before the final exam. These slides do not have all the material delivered during the lectures. Yes, you are supposed to attend them.

Individual 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
• Lectures 11-13: Turing Machines

Exercises	Solutions
Tutorial 1: Sets and functions	Solutions 1
Tutorial 2: Equivalence relations	Solutions 2
Tutorial 3: Cardinality	Solutions 3
Tutorial 4: Automata	Solutions 4
Tutorial 5: Deterministic and non-deterministic automata	Solutions 5
Tutorial 6: NFA = DFA	Solutions 6
Tutorial 7: Pumping Lemma	Solutions 7
Tutorial 8+9: more Pumping Lemma	Solutions 8+9
Tutorial 10: Pushdown automata and context free grammars	Solutions 10
Tutorial 11: Regular Languages, Pumping Lemma 2	Solutions 11
Assignment 1	Solutions
Assignment 2	Solutions

2018 Guest Lectures

• COSC241 Lecture 22: Biological Data Science
• COSC241 Lecture 23: Biological Data Science