COSC341 Theory of Computing
Lecture Schedule
Jump to Lecture slides
- Glossary. A work in progress (Lectures 1–7 so far).
- Languages and problems
To view the lecture recordings, access them via the Lecture Recordings link in Blackboard or log in directly to EchoVideo using your student email address.
- Lecture 1: What is computing?. Tutorial 1. Solutions
- Lecture 2: Automata and grammars. Tutorial 2. Solutions
- Lecture 3: What is computation? - updated after lecture. Tutorial 3. Solutions
- Lecture 4: Non-determinism and regular languages - updated after lecture. Tutorial 4. Solutions
- Lecture 5: It’s all the same - updated after lecture. Whiteboard scribblings. Tutorial 5. Solutions
- Lecture 6: From language to DFA. Tutorial 6. Solutions
- Lecture 7: Minimising automata. Tutorial 7.
- Lecture 8: More on minimising automata.
- Lecture 9: Pushdown automata and context-free grammars. Notes on my tablet. Tutorials 9 and 10. Solutions
- Lecture 10: More on context-free languages; The pumping lemmas (same slides as Lecture 9).
- Lecture 11: Introducing Turing machines. Tutorial 11: Turing machines.
- TM simulator code for w#w as done in class. Diagram of states and transitions
- Lecture 12: More Turing machines. Tutorial 12: Turing machines.
- Lecture 13: Enhanced Turing machines. Additional details. Tutorial: See exercises at end of Notes 11. Solutions.
- Lecture 14: Recursivity and the universal Turing machine. Tutorial: See exercises at end of Notes 12. Solutions.
- Lecture 15: Undecidability of the halting problem. Tutorial: See exercises at end of Notes 13. Solutions.
- Lecture 16: P and NP. Tutorial: See exercises at end of Notes 14. Solutions.
- Lecture 17: Polynomial reductions and NP-hardness. Supported by Notes 15. Tutorial: See exercises at end of Notes 15. Solutions.
- Lecture 18: Propositional logic and satisfiability. Supported by Notes 16. Tutorial: See exercises at end of Notes 16. Solutions.
- Lecture 19: The Cook-Levin theorem.
- Lecture 20: Example deductions (3-SAT and Independent-Set)
- Lecture 21: More reductions (3-SAT to 3-Colouring and to Hamiltonian-Circuit). Template draw.io files for tutorial:
- Ternary or-widget from 3-SAT to 3-Colouring to colour (draw.io file))
- 3-SAT to directed Hamilton cycle graph to complete (draw.io file)
- Lecture 22: Yet more reductions and search (Subset-Sum and Fair-Division). Tutorial: See exercises at end of Notes 19. Solutions.
- Lecture 23: Matchings
- Lecture 24: Fixed-parameter tractability and approximation
- Lecture 25: Student presentations
- Lecture 26: The big finish
The notes reflect the old version of teaching the paper, i.e., they start with the mathematical background required. I’ve chosen to include that here since it’s useful as reference material if you’re feeling a bit unsure about some things. Roughly speaking the lecture material for us starts from the fourth part, dipping back into the first three as needed.
- Part 1: Mathematical preliminaries
- Part 2: Equivalence and cardinality
- Part 3: Recursion and induction
- Part 4: Languages and finite-state automata
- Part 5: Non-determinism and regular languages
- Part 6: Not regular languages
- Part 7: What is computation (goes with lecture 3).
- Part 8: Pushdown automata
- Part 9: Introduction to Turing machines
- Part 10: More Turing machines
- Part 11: Enhanced Turing machines
- Part 12: Recursivity and the universal Turing machine
- Part 13: Undecidability of the halting problem
- Part 14: Time complexity
- Part 15: P, NP, and polynomial time reduction
- Part 16: Propositional logic and satisfiability
- Part 17: The Cook-Levin theorem
- Part 18: Reductions galore
- Part 19: Even more reductions
- Part 20: Matchings, polynomial and otherwise
- Part 21: Fixed-parameter tractability and approximation