Título: El algoritmo de Huang
Directora: Verónica Becher
Jurados: Nicolás Álvarez y Martín Mereb

Resumen:
Fijemos un alfabeto. Una secuencia de De Bruijn de orden n es una secuencia de símbolos del alfabeto que contiene todas las palabras de longitud n exactamente una vez. Estas secuencias fueron descubiertas y redescubiertas más de una vez a partir de finales del 1800. En este trabajo analizamos el algoritmo de Yuejiang Huang del año 1990 que produce secuencias de Bruijn en un alfabeto de dos símbolos. Es un algoritmo óptimo en tiempo y memoria, que arroja secuencias de Bruijn muy balanceadas, esto significa que en cada segmento de la secuencia los dos símbolos del alfabeto aparecen casi la misma cantidad de veces. Mostramos aquí de qué manera el algoritmo de Huang construye una secuencia de Bruijn de orden n definiendo un camino Euleriano en el grafo de Bruijn de orden n-1, uniendo una clase particular de ciclos simples.