May 2019

This note gives a list of theoretical problems that are important to computer science. It is meant to be regularly updated with the various finds dug out from some bibliographical excavations.

Knight's tour | Instance of the Hamiltonian cycle finding problem with a simple heuristic (Warnsdorff's rule) |

N-Queens | Simple example to illustrate backtracking |

Stable marriages | Reference problem when considering offer/demand systems |

Post's correspondance problem | Often used to prove the undecidabilty of some decision problem |

Wang tiles | Useful for procedural generation: with as few as 11 basic tile patterns, a plane can be tiled aperiodically |

Rule 110 | Similar to Wang tiles, to the difference that it displays a high amount of near similar patterns |

Equational logic | Convenient for a logical (or computational) introduction to abstract algebras |

Unbounded nondeterminism | Well-known problem when considering concurrent systems |