Content
This module is a mix of topics, mostly mathematical, which are of use to computer scientists. At first sight they may appear fairly disconnected but they are in fact all closely related.
The specific topics covered are:
- Formal languages (regular, context free, etc.)
- Logic (propositional calculus, first order logic)
- Numbers
- Sets (finite, countable, uncountable)
- Trees and graphs
- Idealised machines (finite state automata, pushdown automata, Turing machines)
- Algebra (semigroups, monoids, groups)
Text
I will provide lecture notes for the material from the first semester. These are in pdf and html formats. The notes cover more than I can cover in lectures and I will mostly try to present different examples in the notes and in lectures. Unless a topic is explicitly described as not examinable you should assume that you are responsible for the contents of both the notes and the lectures.
I am trying to make them accessible to visually impaired students to the extent that I can but the technology for typesetting mathematics is not particularly screen reader-friendly. If you use a screen reader please contact me since I'm interested in trying to make the experience less awful.
In addition to the notes there are three books on reserve in the library:
- Introduction to the theory of computation by Michael Sipser,
- Proof, Logic, and Conjecture: The Mathematician’s Toolbox by Robert S. Wolf, and
- A beginner's guide to mathematical logic by Raymond Smullyan.
Exams
There will be single exam in the usual exam period, worth 60% of your module mark.
Assignments
There are weekly assignments for this module, worth 40% of your module mark.
| Assignment | Due | Problems | Solutions |
|---|---|---|---|
| 0 | 2023.09.22 | ||
| 1 | 2023.09.29 | ||
| 2 | 2023.10.06 | ||
| 3 | 2023.10.13 | ||
| 4 | 2023.10.20 | ||
| 5 | 2023.11.06 | ||
| 6 | 2023.11.10 | ||
| 7 | 2023.11.17 | ||
| 8 | 2023.11.27 | ||
| 9 | 2023.12.01 |
Lectures
| Lecture | Date | Topic(s) | Slides |
|---|---|---|---|
| 0 | 2023.09.12 | Introduction | |
| 1 | 2023.09.14 | Formal Languages | |
| 2 | 2023.09.15 | Formal Languages | |
| 3 | 2023.09.19 | Formal Languages | |
| 4 | 2023.09.21 | Languages, Logic | |
| 5 | 2023.09.22 | Zeroeth Order Logic | |
| 6 | 2023.09.26 | Zeroeth Order Logic | |
| 7 | 2023.09.28 | Zeroeth Order Logic | |
| 8 | 2023.09.29 | First Order Logic | |
| 9 | 2023.10.03 | First Order Logic | |
| 10 | 2023.10.05 | Non-deterministic computation | |
| 11 | 2023.10.06 | First order logic | |
| 12 | 2023.10.10 | Elementary arithmetic | |
| 13 | 2023.10.12 | Elementary arithmetic | |
| 14 | 2023.10.13 | Set theory | |
| 15 | 2023.10.17 | Set theory | |
| 16 | 2023.10.19 | Set theory | |
| 17 | 2023.10.20 | Set theory | |
| 18 | 2023.10.31 | Set theory | |
| 19 | 2023.11.02 | Graph theory | |
| 20 | 2023.11.03 | Graph theory | |
| 21 | 2023.11.07 | Graph theory | |
| 22 | 2023.11.09 | Abstract algebra | |
| 23 | 2023.11.10 | Abstract algebra | |
| 24 | 2023.11.14 | Abstract algebra | |
| 25 | 2023.11.16 | Regular languages | |
| 26 | 2023.11.17 | Regular languages | |
| 27 | 2023.11.21 | Regular languages | |
| 28 | 2023.11.23 | Regular languages | |
| 29 | 2023.11.24 | Regular languages | |
| 30 | 2023.11.28 | Regular languages | |
| 31 | 2023.11.30 | Context free languages |
Due to unavoidable schedule conflict Lecture 16 and Lecture 21 were prerecorded.
Tutorials
There are weekly tutorials. You will be split into two groups for the tutorials. These will probably start in the second week, depending on when we get a tutor assigned.
Blackboard
There is also a Blackboard page for this module. I will try to post everything both here and there but I will occassionally forget. If you notice I've posted something in one place but not the other please let me know.