Subsections
Lecture Notes
The notes will be very sparse; I will only put in them definitions and
the like (and maybe some worked, tedious exercises). The rest of the
matter will be discussed on the blackboard; these notes are just a
mean to save some writing (and so some time).
- Alphabets and languages
(handout
and
overhead presentation): This set
includes some mathematical preliminaries and a discussion on the
math of strings of symbols (which will be our bread and butter for
the remainder of the course). This covers Chapter 1 from the
textbook; in this particular instance it is probably not necessary
to read the chapter in advance (but it will certainly not hurt if
you do).
- Finite automata (handout
and overhead presentation): These
lectures cover Chapter 2. Most of you have seen most of it in
earlier courses so I expect to go through this chapter fairly
quickly; make sure you read in advance ask questions as needed,
otherwise the chapter will be finished before you know it.
- Context-free languages
(handout
and
overhead presentation): We now
cover Chapter 3 (except Sections 3.6 and 3.7). Said sections (3.6
and 3.7) are covered however briefly in our talk about
deterministic context-free languages
(handout
and
overhead presentation).
- Turing machines (handout
and overhead presentation): These
lectures cover most of Chapter 4. We now reach a general model of
computation. For the time being we define the model (and a few
variants); we will see what we can do with this model later in the
course.
- Computability
(handout
and
overhead presentation):
Includes a discussion on the universal Turing machine and the
Church-Turing thesis. This is all covered in Chapter 7 (with
Section 5.7 covered to a lesser degree).
- Complexity (handout
and overhead presentation) is
the a substantial section of this course. It covers Chapters 6 and
7 (less Section 7.4).
- We conclude with a brief presentation of Other
Turing-complete models
(handout
and
overhead
presentation)
- Introduction:
Lecture 1
(recorded from within Microsoft Teams, apologies for the quality)
- Math, strings, languages:
Lecture 2,
Lecture 3
(recorded from within Microsoft Teams, apologies for the quality)
- Finite automata:
Lecture 4 (camera/screen),
Lecture 5 (camera/screen),
Lecture 6 (camera/screen)
- Context-free languages:
Lecture 7 (camera/screen),
Lecture 8 (camera/screen),
Lecture 9 (camera/screen),
first part of
Lecture 10
(recorded from within Microsoft Teams since there was no sound track
in the main recording, sorry)
- Deterministic context-free languages: second part of
Lecture 10
(Teams recording, see above)
- Mid-course review and (some) motivation:
Lecture 11 (camera/screen)
- The Turing machine:
Lecture 12 (camera/screen),
Lecture 13 (camera/screen)
- Computability:
Lecture 14 (camera/screen),
Lecture 15 (camera/screen)
- Complexity:
Lecture 17 (camera/screen),
Lecture 18 (camera/screen),
Lecture 19 (camera/screen),
Lecture 20 (camera/screen),
Lecture 22 (camera/screen)
- Other Turing-complete models:
Lecture 23 (camera/screen)
- The concluding lecture (24) has not been recorded
In most cases there are two videos for each recorded lecture, one
featuring the camera feed and the other featuring a capture of the
front desk screen. The audio track is the same for both videos.
There aren't too many interesting things happening on the screen, so
you should probably start with the camera stream combined with a
separate view of the respective PDF lecture notes. Alternatively, you
can to run both streams simultaneously (one of them muted).
