COSC341

Theory of Computing

Lecture notes/Course Materials 2017

  • Each week the lecture and tutorial (LECT) material will appear online.
  • Once the tutorial has been held, sample solutions (SOL) will be posted.
  • Each lecture has associated readings from the course textbook.


Material Textbook Topic
Intro Lect01 Sol01 1.1, 1.2 Introduction - Preliminaries
Lect02 Sol02 1.4, 1.5 Equivalence and Cardinality

Lect03 Sol03 1.6, 1.7 Recursion and Induction
Lect04 Sol04 2.1 - 2.3 Regular Languages

Lect05 Sol05 3.1 - 3.3 Grammars
Lect06 Sol06 5.1 - 5.3 Finite automata  —  Brendan's finite automata code

Lect07 Sol07 5.4 - 5.7 Non Determinism
Lect08 Sol08 6.4, 6.6 Languages Regular and Irregular

Lect09 Sol09 7.1, 7.4, 7.5 Pushdown automata and context free languages
Lect10 Sol10 8.1 - 8.3 Turing machines   —   A "working" Turing machine
Lect11 Sol11 8.1 - 8.3 Turing machines
Lect12 Sol12 8.4 - 8.7 Different kinds of Turing machines and the Church-Turing thesis

Lect13 Sol13 8.8, 9.1, 9.2 Turing machines and computable functions
Lect14
 
 
none
 
 
11.1, 11.2,
11.4, 12.1
 
The halting problem
      proof of the undecidability of
      the halting problem in verse form

Lect15
 
Sol15
 
11.3, 11.5,
12.2, 12.3
Problem reducibility
 

Lect16
 
Sol16
 
14.2 - 14.4,
15.1, 15.2
Performance and Complexity
Note this link
Lect17
 
Sol17
 
15.3 - 15.7
 
Polynomial reducibility, NP-hard, NP-complete
 
Lect18and19 Sol18+19 15.8 Cook's Theorem (1)
^ ibid ^
 
 
15.8, 16.1, 16.2 Cook's Theorem (2) | Proof of Cook's Theorem
 
 

Lect20 Sol20 16.2, 16.3 Beyond 3-SAT
Lect21 Sol21 16.3 Graph-theoretic NP-complete problems

Lect22 Sol22 16.3, 16.4 The landscape of NP-complete problems
Lect23 Sol23 16.5 NP-complete optimisation problems

Lect24 Sol24 16.6 Coping with NP-completeness (1)
Lect25 Sol25 16.7 Coping with NP-completeness (2)



Page maintained by Robert                     Last updated:  8th Jun 2017   01:18