A medida que comenzamos a planificar la próxima edición de Introducción a los algoritmos (CLRS), ¿qué debemos agregar y qué debemos eliminar si la cuarta edición no puede ser más grande que la tercera?

Me hubiera gustado ver estos temas agregados:

• Pruebas de conocimiento cero : cuando tomé 6.046 en el MIT, cubrimos ZKP en clase y fue el único tema fuera de CLRS ese semestre. Fue bastante interesante y combinó bien con RSA (los instructores fueron Rivest y Goldwasser) y el otro material. Podría reemplazar la prueba de primalidad o la factorización de enteros. Aunque en realidad no cabe en el capítulo “Algoritmos teóricos de números”.
• Una visión general de la Actualización de Impulso / Pesos Multiplicativos también sería extremadamente útil en mi opinión. Dado el hecho de que los algoritmos de aprendizaje son cada vez más importantes en CS teórica y ML, creo que podría encontrar un lugar en el libro. Podría ir a la sección de algoritmos de aproximación, por ejemplo, en lugar de la suma de subconjuntos. Una propuesta más ambiciosa es que se incluye una sección completa para el aprendizaje de algoritmos . Lo pondría en lugar de algoritmos multiproceso o coincidencia de cadenas.

Sugeriría contra la eliminación de la programación lineal o FFT.

Si bien me encanta el rigor de los grandes libros de algoritmos y, en particular, la Introducción a los algoritmos, un problema general que he encontrado con los libros de texto de algoritmos como profesional de la industria es que se enfocan mucho en estructuras avanzadas de datos que no se usan con frecuencia, y no lo suficiente en las estructuras de datos persistentes que usa mucho.

Para las estructuras de datos centrales, en la mayoría de los casos, las listas, las matrices y las tablas hash son, con mucho, las estructuras más utilizadas. Claro que de vez en cuando puede ver una lista de omisión aquí y allá o aprender que una implementación particular se basa en un árbol equilibrado particular, pero en su mayor parte ensuciarse las manos con estructuras centrales complejas es raro.

Por otro lado, las estructuras de datos persistentes que uno encuentra ahora son mucho más exigentes que cualquier cosa que vea en un libro de texto y, por lo general, mucho menos explicadas. Hay problemas de simultaneidad, confiabilidad y jerarquía de memoria que son muy complejos y rara vez se captan bien en los libros de texto.

Puede haber cierta superposición con parte de este material y una base de datos o clase de sistema operativo, pero en esas clases el análisis algorítmico no es tan riguroso.

Entonces, si pudiera tener una solicitud de función para el próximo libro, sería que hubiera mucho más material adicional centrado en estructuras de datos persistentes.

Actualización sobre qué eliminar:
Si tuviera que elegir, votaría por clasificar redes, programación lineal, FFT y geometría computacional.

Aquí están mis dos centavos sobre lo que se puede arrojar:

Algoritmos parametrizados y multivariados
Recientemente, existe un gran y próspero cuerpo de investigación en el campo de los algoritmos parametrizados; particularmente en el desarrollo de algoritmos exactos para problemas difíciles. Dado lo teórico (en cierto sentido, analizar la complejidad de un algoritmo en función de múltiples parámetros siempre parece ser mucho en comparación con un análisis del peor de los casos basado solo en el tamaño de entrada) y práctico (una gran fracción de problemas prácticos son, de hecho, difíciles de calcular; y hay situaciones genuinas, como algoritmos de votación, donde las soluciones aproximadas pueden ser de interés limitado) importancia de estos algoritmos para la informática moderna, creo que los algoritmos parametrizados merecen un capítulo en un tratado introductorio en algoritmos.

La sección probablemente podría introducir la noción de análisis parametrizado e introducir algunos conceptos elementales utilizados para el diseño de algoritmos FPT como la búsqueda de profundidad limitada y la kernelización .

Streaming y algoritmos sublineales
Los algoritmos para manejar conjuntos de datos enormes son cada vez más relevantes en los últimos años, y solo lo serán en la próxima década. Los aspectos fundamentales de la ciencia de datos y las técnicas algorítmicas como la transmisión, el boceto, el muestreo y los algoritmos sublineales se podrían introducir en uno o dos capítulos.

En cuanto a los temas a eliminar, creo que los capítulos sobre montones de Fibonacci y árboles de Van Emde Boas probablemente pueden desaparecer. Además, el tratamiento en algoritmos gráficos probablemente se puede comprimir; por ejemplo, fusionando los dos capítulos en los caminos más cortos en uno solo.

Empecé a estudiar Introducción a los algoritmos por cuenta propia hace unas semanas, y todavía estoy en la sección Fundamentos . Hasta ahora, creo que el contenido es excelente, pero hay algunas cosas que me gustaría modificar.

1. Cambiar la indexación

El libro usa el índice 1 como la dirección inicial o base de cualquier matriz en sus pseudocódigos. Cada vez que voy a probar un algoritmo a través de un programa, sufro mucho mientras lucho con la falta de coincidencia de indexación, ya que todos los lenguajes de programación que conozco usan indexación de base cero. (No estoy seguro de si existe un lenguaje de programación que comience a contar desde 1; el lenguaje que estoy usando es el C simple con el compilador de GCC.) Estoy seguro de que los otros lectores, a quienes les gusta aplicar sus conocimientos de algoritmos en programación, se beneficiarán enormemente de este pequeño pero poderoso cambio.

2. Discuta la parte del análisis con mayor detalle.

En referencia a la tercera edición del libro, el segundo capítulo, Primeros pasos, analiza el algoritmo INSERTION-SORT (A). El análisis incluye dos columnas en cada fila para cada línea de pseudocódigo: costo y tiempos. Si bien la columna que contiene el costo es directa y simple, no está claro cómo algunas de las líneas obtuvieron su contribución de tiempos (líneas 5, 6 y 7 en particular). Tuve que retroceder y pasar varias horas para obtener su tiempo , que de lo contrario podría haberse gastado en aprender nuevos temas. (Sí, está bien, puedes llamarme un aprendiz lento).

3. Proporcione las respuestas a los ejercicios y problemas.

No estoy pidiendo soluciones completas, pero las respuestas a (casi) todos los problemas serían muy útiles para verificar las respuestas que obtengo. Puedo resolver los problemas, pero generalmente nunca sé si mis soluciones son correctas o no. En cuanto a las preguntas que exigen escribir pseudocódigos, siempre puedo verificar mi pseudocódigo implementándolos en C, pero no se puede decir lo mismo sobre las preguntas matemáticas, o en ocasiones conceptuales, que aparecen de vez en cuando. (Como, por ejemplo, calcular la complejidad temporal del fragmento de código dado para la regla de Horner es una tarea desafiante para un estudiante lento como yo, y no estoy seguro de si el resultado que obtuve es correcto). apéndice que contiene respuestas a ejercicios y problemas. Algunos libros tienden a proporcionar respuestas a preguntas impares . Usted puede hacer eso también. Mantenga los números impares, los matemáticos o conceptuales que exigen una verificación cruzada, y las preguntas restantes como algoritmos o pseudocódigos. Hagas lo que hagas, solo proporciona las respuestas a las preguntas, fáciles o difíciles.

No me malinterpretes. Creo que CLRS es un gran libro y una gran herramienta para un estudiante universitario como yo, pero creo que ciertas partes deben mejorarse.

PD: Me gustaría recordarles que acabo de comenzar a leer el libro y no estoy en posición de juzgarlo. Puedo volver con más sugerencias una vez que (con suerte) complete una parte sustancial de ella. Sin embargo, eso llevará algún tiempo.

Añadir

1. Estructuras de datos probabilísticas: filtro Bloom, hashing sensible a la localidad, Minhash, listas de omisión
2. Algoritmos de optimización como recocido simulado, agrupación de k-medias, vecino más cercano
3. Algoritmos distribuidos y Map-Reduce
4. Estructuras de datos distribuidos, como tabla grande y matriz dispersa.
5. Lista de adyacencia, conjuntos anidados, árboles Scapgoat
6. R-Trees / Quadtrees, Kd-trees y Interval trees. Pueden ser árboles BSP, árboles Hash y árboles Fenwick pueden ser buenos como ejercicio.
7. Introducción a estructuras de datos puramente funcionales como Finger Trees
8. String Matching (Capítulo 32): árboles Trie y BK
9. Algoritmos gráficos básicos (Capítulo 22): A *, isomorfismo del subgrafo, cierre transitivo

Expandir

1. Método Akra-Bazzi
2. Flujo máximo con algoritmo húngaro, algoritmo de matrimonio estable
3. Geometría de Computación (Capítulo 33) con punto de búsqueda en polígono
4. Hashing perfecto con Hashing mínimo perfecto

Contrato

1. Medianas y estadísticas de pedidos
2. Árboles rojo-negros (¡por favor no los elimines!)
3. Aumento de estructuras de datos
4. Algoritmos codiciosos (pp 423-428 y Matroids)
5. Árboles van Emde Boas

retirar

1. Algoritmo de Strassen para la multiplicación de matrices
2. Montones de Fibonacci
3. Operaciones matriciales
4. FFT
5. Algoritmos teóricos numéricos

Sugiero incluir una introducción a Algoritmos parametrizados y Complejidad parametrizada o Algoritmos en línea , y eliminar Montones de Fibonacci. No elimine la Programación lineal si planea mantener los Algoritmos de aproximación allí (ya que claramente es necesario dentro de la sección Algoritmos de aproximación en su forma actual, ni debería eliminarse). Las técnicas de LP y los algoritmos de aproximación van de la mano constantemente.

Personalmente, creo que el libro es tan relevante como cuando salió la tercera edición. Hay excelentes textos especializados que son más recientes para temas más especializados (como los que sugerí), pero sería algo muy bueno para acompañar los algoritmos de aproximación.

Mi $ 0.02:

• Algoritmos en línea y su complejidad.
• Introducción a algoritmos distribuidos.
• Introducción a algoritmos probabilísticos y estructuras de datos.
• Ejemplos de programación funcional y su análisis de complejidad.

Además, un poco más de énfasis en el hecho de que los algoritmos y las estructuras de datos son un aspecto de la programación, mientras que la ingeniería de sistemas es otro aspecto. Con demasiada frecuencia en estos días veo el código donde un algoritmo útil, práctico y limpio implementado por sí mismo está codificado en otra pieza de arquitectura más grande y torpe. Lo que perjudica gravemente a ambos extremos del espectro.

Añadir:

• Programación competitiva
• Algoritmos de aprendizaje automático
• Programación funcional / cálculo lambda
• Algoritmos combinatorios

Retirar:

• Algoritmo de Strassen para la multiplicación de matrices

No quitar

• Algoritmos teóricos numéricos
• Algoritmos multiproceso

Expandir:

• Divide y conquistaras

Contrato:

• Programación lineal

Otros:

• La complejidad del espacio debe especificarse para muchos algoritmos y estructuras de datos.
• Guía para resolver ejercicios, brindar soluciones en línea
• Mueva secciones avanzadas u opcionales en línea para hacer espacio en el libro

Creo que podría cubrir más amplitud e introducir áreas emergentes en algoritmos. Algunos temas que sugeriré:
1. Algoritmos en línea (relación competitiva, función potencial)
2. Cálculo cuántico (una pequeña introducción con puede ser el algoritmo de Shor).
3. Algoritmos de aproximación (Algoritmo de Christofides para TSP, es simple y mejorarlo es el mayor problema abierto en Approx Algo, algunos LP Duality pueden estar usando set cover)
4. Algoritmo aleatorizado (mincut de Karger, mención de Markov, Chebyshev, el límite de Chernoff en el apéndice matemático)
5. Algoritmo paralelo y distribuido. (introducción básica)
6. Algoritmo de parámetro fijo. (introducción básica)

Encuentro dos mucho estrés se da en las estructuras de datos. Podrías dividir el libro en dos partes:
1. Algoritmos y 2. Estructuras de datos.

Agregue optimizaciones de programación de encuentro en el medio y dinámico. (por ejemplo, ciertos problemas se pueden resolver en [math] O (n ^ 2) [/ math], pero con la optimización se pueden resolver en [math] O (n \ log n) [/ math]. Expandir en heavy- descomposición de luz.
Agregue árboles cortados por enlaces también.
También sugeriría agregar más algoritmos relacionados con cadenas.
Explicar los árboles y las listas de saltos. Son realmente útiles; incluso hay una conferencia de Erik Demaine en las listas de omisión en MIT OpenCourseWare (pero no parece estar en el libro, entonces ¿por qué no agregarlo?)

Agregue un tratamiento detallado en:
– algoritmos ajenos a la memoria caché
– árbol avl
– filtros de floración
– Estimación de cardinalidad
– compresión (que cubre algoritmos de uso común como lz77, lz78, codificación de madriguera hasta paq, etc.)
– regexp y gramática libre de contexto
– árboles LSM
– R árboles
– árboles Kd
– Tratamiento mucho más detallado en algoritmos paralelos.

No creo que deba eliminarse nada, principalmente porque el campo está creciendo y el libro necesita crecer para mantenerse relevante.

¡Qué bueno escuchar las noticias!

Tengo 2 sugerencias:
1. Este parece ser irrelevante, pero sí quiero que el editor divida el libro en 2 fascículos, uno para conceptos básicos y otro para temas avanzados. Es una pesadilla llevar el único libro grueso todos los días.
2. Ustedes pueden construir un proyecto de código abierto o algo más para publicar todos los códigos de ejemplo (no el pseudo uno). Ayudará a aquellos que quieran aprender algoritmos mediante la práctica.

Gracias de nuevo por la nueva edición!

Incluir:
1. Estructura de datos de Trie .
2. Un capítulo completo dedicado a Backtracking.
3. Introducción a los algoritmos de aprendizaje automático (al ver el creciente interés en Big data, IA, aprendizaje automático y minería de datos).

Retirar:
1.programación lineal

Discuta los algoritmos en el contexto de la programación funcional (no con tanta profundidad como Okasaki, por supuesto). Además de discutir las implicaciones de pureza, rigidez / pereza e implicaciones para la complejidad, sería interesante mostrar aplicaciones de lambda y funciones de orden superior. Después de cubrir algunas de las inquietudes, puede pedirle al alumno que haga versiones funcionales en los ejercicios, por ejemplo.

La presentación de solo algoritmos imperativos, en 2014, no parece reflejar cuánto ha cambiado y continuará cambiando el panorama del lenguaje de programación.

Añadir

1. Portada del libro estético. Explore cualquier libro de cualquier tema en Barnes & Nobles en busca de inspiración. El diseño moderno de portadas de libros ha recorrido un largo camino desde 2009.
2. Árboles Merkle. Ver Bitcoin
3. Filtros de floración. Ver Bitcoin
4. Analogías gráficas para el algoritmo OCLA de Tarjan. Algoritmo relativamente simple, pero no podía descifrar cómo funcionaba desde el libro (tenía que hacer referencia al sitio web GeeksForGeeks para incluso comenzar a entenderlo). Las analogías gráficas serían especialmente útiles para mostrar exactamente lo que está sucediendo.
5. Algoritmo de Boruvka. Se habló brevemente en el libro (¿atribuciones de Tarjan?), Pero no se discutió en profundidad. Las diferencias entre Prim, Kruskal y Boruvka pueden ser buenas. Quizás en forma de mesa.
6. Buffers de anillo. Sorprendentemente, no en muchos libros de algoritmos. Estructura de datos extremadamente útil que puede ajustar el espacio / tiempos de ejecución para muchos algoritmos.
7. Enrejados También una estructura de datos que sorprendentemente se ignora en muchos libros de texto de algoritmos.

retirar

1. Esa horrible portada del libro de la primera, segunda y tercera edición. Probablemente mi única queja sobre el libro que siento mucho. Por favor, no te ofendas.
2. Van Emde Boas Árboles. Nunca los escuché ni los usé fuera de este libro.
3. Montones de Fibonacci. Deberíamos saber cómo obtenerlos cuando lleguemos a esta parte del libro. Asumiendo que estamos leyendo secuencialmente.
4. B-árboles. Es difícil deshacerse de esto, pero puedo ver que se ha ido sin causar demasiadas ondas.
5. ???. Decidir qué sacar a continuación es un problema NP-difícil. El libro está bien escrito; no me culpes por no resolverlo.

Qué debes eliminar : Nada.

¿Qué deberías agregar?

• Algunos conceptos básicos:

• Recursividad
• Retroceso
• Gestión de la memoria.
• Plantillas.

• Montones binomiales.
• AA- Árboles.
• B * -árboles.
• B + – Árboles.
• R- Árboles.
• Treaps
• Kd árboles.
• Emparejamiento de montones.
• Listas de salto deterministas.
• Extiende árboles.

• El árbol de expansión mínimo nlog (n).
• La respuesta de Log (n) fibonacci.
• Algunos conceptos y algoritmos avanzados de Graph.
• Algunos algoritmos matemáticos avanzados.
• Algoritmos de teoría de juegos.

Todo eso está en mi mente ahora, actualizaré la respuesta si recuerdo algo más.

Ante todo:

• Usted presenta el algoritmo rho de Pollard para la factorización de enteros al final de la sección Algoritmos teóricos numéricos, pero no el algoritmo “Tortuga y liebre” de Floyd para la detección del ciclo, en el que se basa el método de Pollard. Este es un excelente ejemplo de algoritmo para el que tanto la corrección como la complejidad son sorprendentes, y creo que debería aparecer en el libro.

De hecho, me encantaría ver:

• Filtros de floración

• Suffix Trees y Suffix Arrays (también, la sección Knuth-Morris-Pratt podría acortarse) al final de la sección String Matching.

Y también creo que puedes eliminar:

• Geometría Computacional
• Programación lineal

1. Es hora de dividir el libro en dos volúmenes. Básico y avanzado (idealmente debería terminar como una serie de libros sobre algoritmos).
2. El volumen básico debe tratar con los fundamentos, algo útil que se usa con mucha frecuencia.
3. Volumen avanzado para satisfacer a los curiosos.
4. Mucha gente dice que elimine la programación lineal, pero a menudo se usa en la práctica.
5. Debido a dos volúmenes, ahora hay mucho espacio para satisfacer a un público más amplio.

Mi voto sería agregar Algoritmos olvidados de caché, algoritmos más aleatorizados y retener los árboles de Van Emde Boas (no sabía que estaban allí en el libro, y solo vi el comentario de alguien sobre eso). El árbol vEB es una hermosa estructura de datos y es esencial para los algoritmos de CO.

También sería bueno agregar algo en árboles LSM, árboles fractales, etc. Con alguna información sobre amplificación de escritura, etc.