This page is maintained by Paul Goldberg, teaching FCS in Michaelmas term 2017–18; please re-visit this page since it is updated regularly.
department FCS web page (some past exam papers)
Lectures: 5:00pm on Mondays and Wednesdays, Lecture theatre A, weeks 1 to 8 (official timetable)
Office hours: I will usually be free to talk after lectures.
Classes: Problem-based exercise classes in weeks 3–8.
| Group | tutor/marker | place | time |
| 1 | Giulio Guerrieri | room 051 (check this) | Tuesday 9am note change, weeks 3–8 |
| 2 | Paul Goldberg | room 051 | Thursday 5pm note change, weeks 3–8 |
Hand in exercises by 12 noon on the preceding Friday in the marker’s pigeon hole.
Textbook: Introduction to the Theory of Computation 2nd Edition by Mike Sipser. There are other books that cover all/most of the material in this course, e.g. Models of Computation: exploring the Power of Computing by John E. Savage; Introduction to Automata Theory, Languages and Computation by Hopcroft, Motwani, and Ullman; An Introduction to Formal Languages and Automata by Linz; Computational Complexity by Papadimitriou.
| slides 5 |
intro to predicate logic, and computational aspects |
| slides 4 |
Computational complexity (about 4 lectures) 13.11.17: introduction to the complexity classes P and NP. Polynomial-time reducibility, and we noted the analogy with reductions in the context of proofs of undecidability. The concept of problems that are complete for a complexity class. 20.11.17: propositional logic and Cook’s theorom. 22.11.17: Polynomial-time reductions, e.g. reduction from LATIN SQUARE COMPLETION to SUDOKU |
| slides 3 |
Undecidability (about 2 lectures) lecture 6.11.17: undecidability of the Halting Problem; reductions, and how we can use pre-existing undecidability results to obtain new ones. |
| slides 2 | Slides for 4-5 lectures (context-free languages; Turing machines, recursive languages) Lecture 30.10.17: operation of TMs; deciding versus accepting; Chomsky hierarchy Lecture 1.11.17: Church-Turing thesis (textbook Chapter 3), TMs can do general computation Lecture 25.10.17: Pumping lemma for CFLs; Turing machines. TM example another TM example (examples are useful, but are missing from the slides themselves). Examples of TMs in textbook, pp.142–147 Lecture 23.10.17: get started on equivalence of PDAs and CFGs. (chapter 2.2 of textbook; this result is similar to Kleene’s theorem, showing that 2 different language representations have the same expressive power.) Lecture 18.10.17: recap of pumping lemma and examples. (Exercise: construct a non-regular (formal) language for which the pumping lemma cannot be applied directly to verify that it is not regular.) Intro to pushdown automata and CFGs. |
| slides 1 | Slides for first 2-3 lectures; textbook chapter 0, 1.1; examples on p38 onwards may be helpful. Lecture 9.10.17: general overview and introduction to finite automata. Lecture 11.10.17: reached slide 42; see textbook p44: the operations union, concatenation, and star; see textbook chapter 1.2: Nondeterminism, NFA examples p51 onwards; p55: general idea of proof that every NFA has an equivalent DFA; p59 onwards: detailed proofs of closure properties Lecture 16.10.17: conversion of finite automaton to equivalent regular expression (see Chapter 1.3 of textbook), introduction to Pumping Lemma (Chapter 1.4 of textbook) |
Proofs: what is required, and getting started.
sample proof (of the “union” construction (many other detailed proofs can be found in the textbook)