Proyectos
Esta es la lista de los proyectos. Cada grupo debe realizar un proyecto
durante el semestre. Para elegir un proyecto mándenme un mail
diciendo el nombre del proyecto y los integrantes del grupo (máximo
2). Una vez que les confirmo que se les asignó el proyecto empezaremos
a tener reuniones cortas para ir definiendo lo que se hará. Por
ahora hay sólo 5 proyectos, se irán agregando más a
medida que veamos más material del curso.
Aunque no todos lo digan explícitamente, TODOS los proyectos involucran
implementación.
Los algoritmos se deben diseñar, analizar e implementar. Se deben
hacer pruebas empíricas para reforzar el análisis.
- Percentiles (tomado)
- Arboles Optimos (tomado)
- Cápsula Convexa (tomado)
- Distancia de Edición (tomado)
- Punto Más Cercano (tomado)
- Shell Sort (tomado)
- Heaps de Fibonacci (tomado)
- Heaps Binomiales (tomado)
-
Heaps Mergeables
Buscar en el Aho Mergeable Heaps. Entender los algoritmos y el análisis,
e implementarlos en forma eficiente (observar que esto involucra implementar
un árbol 2-3 eficientemente). Medir su desempeño en tiempo y
espacio, proponer variaciones. Compararlas contra heaps comunes.
Medir el costo de unir dos heaps de este tipo.
- Leftist Heaps (tomado, acepta compañero)
- Skip Lists (tomado)
- Arboles Rojinegros (tomado)
- Splay Trees (tomado)
- B-Trees (tomado)
- Hashing Extendible (tomado)
- Bounded Disorder (tomado)
- k-ésimo Elemento (tomado)
-
Tries y Variaciones
Buscar Tries en la bibliografía, entender los algoritmos y el
análisis. Implementarlos eficientemente, probando distintos compromisos
entre tiempo y espacio. Hacer lo mismo para la variante llamada árboles
Patricia. Comparar experimentalmente las distintas técnicas entre
sí.
-
Tries Binarios y Variaciones
Buscar Tries en la bibliografía, entender los algoritmos y el
análisis. Implementarlos eficientemente para un alfabeto binario.
Hacer lo mismo para la variante llamada árboles Patricia (caso binario),
y para Level-Compressed Tries. Comparar experimentalmente las distintas
técnicas entre sí.
-
Autómatas para Búsqueda Aproximada
Entender la relación entre búsqueda aproximada y
autómatas (de un paper). Implementar eficientemente el autómata
atendiendo al tiempo de construcción y a la eficiencia en espacio.
Medir experimentalmente, y comparar además los tiempos de búsqueda
contra otras implementaciones (ya escritas) de búsqueda aproximada.
- Filtros para Búsqueda Aproximada (tomado)
- Búsqueda Aproximada en Dos Dimensiones (tomado)
-
Búsqueda Aproximada en Grafos de Texto
Entender de dos papers dos algoritmos de búsqueda aproximada en grafos de
texto. Implementarlos y medir experimentalmente su desempeño.
- Arboles de Sufijos (tomado)
- Arreglos de Sufijos en Disco (tomado)
-
Arreglos de Sufijos en Memoria
Buscar en la bibliografía Arboles de Sufijos (Suffix Trees, a veces
llamados Position Trees) y Arreglos de Sufijos (Suffix Arrays). Entender la
relación y el algoritmo para construir el Arreglo de Sufijos cuando
entra en memoria.
Implementar el algoritmo eficientemente atendiendo a tiempo y espacio, y
compararlo experimentalmente con la implementación naive.
Medir el desempeño experimentalmente para tiempo y espacio de
construcción y para búsquedas.
- Búsqueda en Arreglos de Sufijos sobre Disco Magnético (tomado)
- Aho-Corasick (tomado)
- Boyer-Moore Multipatrón (tomado)
- Expresiones Regulares con Paralelismo de Bits (tomado)
-
Arboles Burkhard-Keller
Entender (de un paper) los BK-trees para búsqueda aproximada en
espacios métricos generales. Analizar su desempeño e
implementarlos eficientemente, variando los parámetros y proponiendo
otras mejoras. Probar distintas estrategias para buscar el elemento más
cercano a una query. Proponer estrategias para almacenar las hojas en el disco.
- FQ-trees (tomado)
-
VP-trees y GH-trees
Entender (de un paper) los VP-trees y GH-trees para búsqueda aproximada
en espacios métricos generales. Analizarlos e
implementarlos eficientemente.
Variar los parámetros y proponer otras mejoras. Probar distintas
estrategias para buscar el elemento más cercano a una query.
Proponer estrategias para almacenar las hojas en el disco.
- GNAT (tomado)
- Fastmap (tomado)
-
R-trees
Entender (de un paper) los R-trees para búsqueda espacial en el
plano. Implementar eficientemente los R-trees, variando los parámetros y
proponiendo alternativas (heurísticas para construir el árbol y
para buscar).
- Hashing Lineal (tomado)
- Hashing Cerrado (tomado)
- Arboles Aleatorizados (tomado)
- Biconectividad y Conectividad Fuerte (tomado)
- Arbol Generador Mínimo (tomado)
- Problema del Viajante de Comercio (tomado)
-
Coloreo de Grafos
Buscar en la bibliografía el problema de Graph Coloring.
Entender la prueba de NP-completitud. Buscar y
proponer distintas heurísticas o algoritmos aproximados
para resolverlo. Implementarlas
eficientemente y medir experimentalmente cuáles funcionan mejor
en qué casos.
-
Knapsack y Bin-Packing
Buscar en la bibliografía estos problemas.
Entender la prueba de NP-completitud. Buscar y
proponer distintas heurísticas o algoritmos aproximados
para resolverlos (algunos tienen cotas de optimalidad). Implementarlas
eficientemente y medir experimentalmente cuáles funcionan mejor
en qué casos.