COSC341

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
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