Computer science
Formal languages
What a formal language, an alphabet and a string are. The basic concepts of formal language theory, explained by comparison with ordinary language and through examples.
Finite automata
A finite-state machine as a model of computation with states and transitions. Definition, state diagram, formalisation of a computation and examples of accepted strings.
Minimising finite automata
Unreachable states of a finite automaton, which cannot be reached from the start state. The definition and how to remove them safely.
Closure properties of regular languages
Regular languages are closed under union, intersection, concatenation and Kleene closure. What closure under an operation means and why it holds for regular languages.
Regular expressions
What a regular expression is and how it describes a set of strings. The definition, a comparison with arithmetic expressions and the link to finite automata.
Estimating the number of distinct values
Linear counting: how to estimate the number of distinct values in large data sets. Hash functions, bitmaps and why the naive approach is not enough.
Bloom filter: is an element in the set?
A Bloom filter is a probabilistic data structure that quickly tells you whether an element is in a set. The principle, hash functions and practical use.
Caesar cipher
How the Caesar cipher works, one of the oldest ways of encrypting text. The principle of shifting letters, a generalisation of the cipher and an online encryption tool.
Vigenère cipher
The Vigenère cipher uses several alphabets, so it withstands frequency analysis. The principle of encryption, the Vigenère square, choosing a key and an online tool.
