DFA simulation C++ implementation

Here, I provide C++ implementation of a table-based Deterministic Finite Automaton. A DFA is a finite state machine that accepts/rejects finite strings of symbols and has a unique transition from each state on each input symbol.

Continue reading

Advertisements

Median of a dynamic list

Here, I discuss the problem of maintaining the running median of a list when numbers are added and removed from the list. The straightforward solution of keeping the list sorted takes constant time per median calculation but linear time per addition/deletion. It would be too slow for our purpose.

Continue reading