Tutorial notes

These notes arise out of problems that have been discussed in tutorials or elsewhere. Some other notes are accessible to tutors.

• Splay trees – a reminder.
• Termination of tree rotations.
• Some problems to begin with.
• An SIMD approach to an image smoothing problem.
• A family of Haskell expressions whose types grow exponentially.
• A problem associated with the Twelve Days of Christmas.
• A note entitled Kicking around a binomial sum, and another note about a different sum.
• My standard story for explaining the idea of duality in linear programming.
• A note about what WeakHashMap is good for in Java.
• A note on twice twice twice.
• A handy list of design patterns in Object-Oriented Programming.

Automata theory

Alluding to Lakatos, Automata theory sometimes seems caught in the death-like grip of the Euclidean Programme. Here are some antidotes to help mere mortals and humble programmers understand it.

• A note about places where arguments about automata can be streamlined.
• A note about invariants for an algorithm that decides equivalence of deterministic finite automata.
• Hints about deriving regexps from finite automata.