Material adicional

• De tipo general:
• A subset of the slides of the course in English (for a ten hours course).
• Sobre Ada y GNAT.
• Un diccionario (colección de palabras) de 113801 palabras en inglés. Una página sobre colecciones de palabras.
• “Chuleta” de fórmulas (autor: Steve Seiden).
• Transparencias de Esquemas Algorítmicos (curso 2000-01).
• Fe de erratas de libros:
• Erratas del libro [CLR90].
• Más erratas de [CLR90].
• Erratas del libro [Knu73].
• Material introductorio sobre eficiencia de algoritmos:
• Apuntes de J.L. Balcázar.
• Material sobre árboles rojinegros:
• Un applet para manipular árboles rojinegros (seleccionar “R-B”) (acceso mediante clave).
• Otro applet.
• Otro más.
• Implementación más eficiente, top-down (tutorial y código C++; capítulo de libro de Weiss con código Java; código Ada95 de Weiss: ads, adb).
• Algo de material sobre árboles AVL (para el que quiera repasar):
• Transparencias de la lección 14.
• Código.
• Material sobre montículos d-arios:
• Transparencias de J. Turner, de la Universidad de Washington.
• Material sobre tries, árboles digitales y Patricia:
• Capítulo sobre tries del libro [MS05] de la bibliografía (acceso mediante clave).
• Capítulo sobre árboles digitales, tries y Patricia del libro [Sed98] (acceso mediante clave).
• Coste promedio de búsqueda.
• Transparencias de un seminario de Matthias Rieger en la Universidad de Berna (acceso mediante clave).
• Material sobre árboles ternarios (una implementación de tries):
• Artículo de Jon Bentley y Robert Sedgewick, “Ternary search trees”, en Dr. Dobb’s Journal, April 1998 (copia local, acceso mediante clave).
• Otro artículo de Jon Bentley y Robert Sedgewick, “Fast algorithms for sorting and searching strings”, en Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, January, 1997.
• Implementación en C (demo).
• Otra implementación en C (demo).
• Material sobre Patricia:
• Artículo de Dhamim Packer Ali, “Performance analysis of IP routing lookup algorithms: Patricia tree based vs. hashing based”.
• Artículo de Knessl y Szpankowski, “Limit laws for heights in generalized tries and Patricia tries”.
• Artículo de Rais, Jacquet y Szpankowski, “Limiting distribution for the depth in Patricia tries”.
• Artículo de Tsuchiya, “A Search Algorithm for Table Entries with Non-contiguous Wildcarding” (acceso mediante clave).
• Material sobre listas “skip”:
• Artículo seminal de Pugh, “Skip lists: A probabilistic alternative to balanced trees”, [Pug90a].
• Otro artículo del mismo autor, “A skip list cookbook”, [Pug90b].
• Artículo de Messeguer, “Skip trees, an alternative data structure to skip lists in a concurrent approach”, [Mes97].
• Un applet.
• Otro applet.
• Uno más (con árboles AVL, rojinegros, AA, B, listas skip, heaps, treaps, splay…).
• Material sobre árboles aleatorizados (“treaps”):
• Capítulo del libro de Kozen, “Random search trees”, [Koz92].
• Artículo de Seidel y Aragon, “Randomized search trees” (acceso mediante clave).
• Notas de clase de C.K. Yap, “Random Search Trees”, [Yap00].
• Artículo de Blelloch y Reid-Miller, “Fast Set Operations Using Treaps”, [BRM98].
• Artículo de Martínez y Roura, “Randomized binary search trees”, [MR98].
• Un applet de demostración de “treaps”.
• Material sobre introducción al análisis amortizado:
• Una clase completa de C.E. Leiserson en el M.I.T (este es el curso completo).
• Montículos binomiales y de Fibonacci:
• Applet de montículo binomial.
• Applet de montículo de Fibonacci. Otro applet.
• Material sobre estructuras de conjuntos disjuntos:
• Capítulo del libro de Cormen et al. de la bibliografía [CLRS09] (acceso mediante clave).
• Artículo de Harfst y Reingold, “A potential-based amortized analysis of the union-find data structure” (acceso mediante clave).
• Artículo clásico de Leiserson sobre aplicación a diseño de circuitos integrados (acceso mediante clave).
• Un applet para visualizar el TAD.
• Otro applet.
• Material sobre estructuras auto-organizativas:
• Artículo de Andrew M. Liao, “Self-adjusting data structures”, en Dr. Dobb’s Journal, February 1990 (copia local, más fácilmente legible).
• Capítulo del libro de Kozen, “Splay trees”, [Koz92].
• Artículo seminal de Sleator y Tarjan, “Self-adjusting binary search trees” (acceso mediante clave).
• Material diverso de Daniel D. Sleator: una “demo” de splay trees, código fuente de splay trees.
• Notas de clase de la Universidad del Estado de San Diego: splay trees y splay tree performance.
• Una visualización de splay trees.
• Otro applet de splay trees.
• Algoritmos de búsqueda exacta de subcadenas:
• El artículo original de Knuth, Morris y Pratt.
• El artículo original de Boyer y Moore.
• El algoritmo de Boyer y Moore tal y como aparecía en la 1ª edición del libro de Cormen et al. (en ediciones posteriores no aparece) (acceso mediante clave).
• Página con applets de visualización de la traza de los algoritmos.
• Libro sobre el mismo tema, de los mismos autores.
• Material sobre árboles de sufijos:
• Informe de Gusfield, “Algorithms on strings, trees, and sequences: Introduction to suffix trees”, similar a un capítulo del libro [Gus97].
• Otro informe de Gusfield, “Algorithms on strings, trees, and sequences: Linear time construction of suffix trees”.
• Capítulo sobre árboles de sufijos del libro [MS05] de la bibliografía (acceso mediante clave).
• Página con demo, código, etc., de generación de árboles de sufijos: Lloyd Allison, Monash University.
• Otra demo, de Moritz G. Maaß, TUM.
• Árboles de sufijos generalizados: artículo de la Universidad de Minesota (acceso mediante clave).
• Alternativas: suffix arrays (Manber y Myers, 1993), suffix vectors (Monostori et al, 2002) (acceso mediante clave).
• A taxonomy of suffix array construction algorithms, Simon J. Puglisi, W. F. Smyth & Andrew Turpin, ACM Computing Surveys 39-2 (2007) 1-31 (acceso mediante clave).
• 7.560.000 enlaces sobre árboles de sufijos.
• Aplicaciones de algoritmos de búsqueda de patrones:
• ¿Qué tiene que ver la informática con la biología?, transparencias de Elvira Mayordomo.
• Aplicación de algoritmos de búsqueda de patrones en robótica móvil.
• Enlace al National Center for Biotechnology Information de EE.UU.
• Beginner’s Guide to Molecular Biology.
• Introducción a la biología molecular, del periódico El Mundo.
• Material de la asignatura COP 5536 Advanced Data Structures del profesor Sartaj K. Sahni de la Univ. de Florida.