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.

  1. Percentiles (tomado)

  2. Arboles Optimos (tomado)

  3. Cápsula Convexa (tomado)

  4. Distancia de Edición (tomado)

  5. Punto Más Cercano (tomado)

  6. Shell Sort (tomado)

  7. Heaps de Fibonacci (tomado)

  8. Heaps Binomiales (tomado)

  9. 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.

  10. Leftist Heaps (tomado, acepta compañero)

  11. Skip Lists (tomado)

  12. Arboles Rojinegros (tomado)

  13. Splay Trees (tomado)

  14. B-Trees (tomado)

  15. Hashing Extendible (tomado)

  16. Bounded Disorder (tomado)

  17. k-ésimo Elemento (tomado)

  18. 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í.

  19. 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í.

  20. 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.

  21. Filtros para Búsqueda Aproximada (tomado)

  22. Búsqueda Aproximada en Dos Dimensiones (tomado)

  23. 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.

  24. Arboles de Sufijos (tomado)

  25. Arreglos de Sufijos en Disco (tomado)

  26. 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.

  27. Búsqueda en Arreglos de Sufijos sobre Disco Magnético (tomado)

  28. Aho-Corasick (tomado)

  29. Boyer-Moore Multipatrón (tomado)

  30. Expresiones Regulares con Paralelismo de Bits (tomado)

  31. 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.

  32. FQ-trees (tomado)

  33. 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.

  34. GNAT (tomado)

  35. Fastmap (tomado)

  36. 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).

  37. Hashing Lineal (tomado)

  38. Hashing Cerrado (tomado)

  39. Arboles Aleatorizados (tomado)

  40. Biconectividad y Conectividad Fuerte (tomado)

  41. Arbol Generador Mínimo (tomado)

  42. Problema del Viajante de Comercio (tomado)

  43. 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.

  44. 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.