Brainstorm de algoritmos

Brainstorm de ideas de temas algorítmicos para desarrollar, en forma de lista. Muchísimos de estos temas exceden el nivel usual de la IOI / competencias de nivel secundario, siendo más avanzados y adecuados para nivel universitario, ya que esta lista se inició a partir de una ya existente lista de temas apuntada a la competencia de programación universitaria ACM-ICPC.

Algunos no son necesariamente más avanzados pero están al momento de escribir estas líneas “explicitly excluded” en el Syllabus de IOI.

No obstante, como lista ideas, con temas existentes posibles para desarrollar, no deja de ser una lista valiosa para generar material apuntado a OIA y competencias de nivel secundario.

Grafos
- Representación de grafos en memoria
  - Matriz de Adyacencia
  - Matriz de Incidencia
  - Listas de Adyacencia
  - Lista de incidencia
  - Grafo Implícito
- BFS
  - Basico.
  - BFS con cola de dos puntas [Aristas 0 y 1]
  - BFS con K+1 bolsas [aristas 0..K]
  - Truquito “ahorrar aristas”: Ajedrez, Alfil
- DFS
  - Back Edges
  - Tree Edges
  - Forward Edges
  - Cross Edges
  - Aplicaciones posibles
- Dijkstra
  - En N^2
  - En (N + M) lg N
  - Distancia Min-Max
- Bellman-Ford
  - Vision como programacion dinamica.
  - Implementacion tipica.
  - Variante para contar caminos entre pares de nodos.
- Floyd-Warshall
  - Vision como programacion dinamica.
  - Implementacion tipica.
  - Variante para contar caminos entre pares de nodos.
- Dantzig (presentación similar a Floyd, pero observando que este es incremental en nodos).
- Producto de matrices de adyacencia / Potencias de la matriz de adyacencia.
- Reconstrucción de caminos en algoritmos de camino mínimo
  - Guardando padres
  - Chequeando la cuentita de la DP
  - Truquito de dar vuelta origen y destino (y trasponer el grafo si es dirigido) así al recorrer los padres queda el camino al derecho.
- Detección y tratamiento de ciclos negativos
  - Con Floyd
  - Con Bellman Ford
- Prim
  - Descripción e implementación
  - Relación con Dijkstra
- Kruskal
  - Descripción e implementación, con referencia a Union-Find
- Relación del Minimum Spanning Tree con la distancia Min-Max.
  - Aplicación a calcular la distancia min-max todos contra todos en N^2
  - Solución alternativa para el mismo problema: hacerlo en el mismo Kruskal que calcula el MST
- Matching Maximo Bipartito
- Flujo y derivados:
  - Flujo Maximo / Corte Minimo
  - Edmonds-Karp
  - Dinitz
  - Scaling (para flujo + idea general)
  - Algoritmos de Preflow-Push
  - Manejo, entendimiento y manipulación de la red residual de un grafo.
  - Teoremas de König, Hall y Menger.
  - Mínimo Cubrimiento por Caminos. Mínima Partición en Caminos. Teorema de Dilworth
  - Flujo de costo minimo.
- DAGs:
  - Ordenamiento Topologico
  - Clausura transitiva (aplica a cualquier grafo pero es muy común en DAGs)
- Componentes Biconexas (Puntos de articulación, puentes)
- Componentes Fuertemente Conexas
- Camino/Ciclo euleriano
- Teoremas de Ore + Dirac (Sobre todo la demo, que permite eficientemente encontrar un ciclo hamiltoniano en un grafo que cumple las hipótesis)
- Árboles:
  - Detección,recorrido.
  - Representación de arboles con raíz.
    - Padre de cada nodo
    - Lista de adyacencia del dirigido “bajando desde la raíz”.
  - Radio, centro y diámetro de un árbol en tiempo lineal.
  - Centroid decomposition
  - Prufer codes
- Grafos planares
  - Fórmula de Euler
  - Los grafos planares son ralos
  - Dualidad
  - Grafo dual
Análisis de complejidad
- Entendimiento de la notacion asintotica (La O grande de “O(N)”)
- Analisis amortizado de complejidad
- Nocion de P, NP, NP completo, algoritmo polinomial, etc
  - Problemas NP completos conocidos
  - Problemas que no se sabe que estén en P ni se sabe que sean NP completo (Factorización entera, logaritmo discreto, isomorfismo de grafos)
Algoritmos de Ordenamiento
- Busqueda lineal y busqueda binaria (con LA RECETA)
- Counting Sort
- MergeSort
- QuickSort
- Mediana (o elemento iesimo) en tiempo lineal esperado
- HeapSort
- BubbleSort
- InsertionSort
- RadixSort
Estructuras de datos
- Arreglos
- “Truco del arreglo autolimpiante”
- STL (set, multiset, map, multimap, vector, queue, stack, deque, priority_queue, list, etc)
- Listas enlazadas
- Colas
- Pilas
- Tries
- Hashing
- Árbol binario de búsqueda (TREAP)
- Heap (para priority queue), heapsort, heapify en O(N)
- Union Find (Implementacion con listas y con arbol, la de listas es facil de codear y permite iterar las componentes, se aplica al problema Hackers de la local de UBA 2010)
- RMQ (Segment tree sobre arreglo) (Updates con recalculo vs acumulativos) (Multi Dimension)
- Sliding Windows, Sliding-RMQ (para en O(N) calcular el RMQ de subarreglos de un tamaño K dado)
- Variante de sliding window RMQ con dos 2deque para guardar los dos mejores
- “La DP de Huguito” (anda para cualquier operador asociativo, eso incluye “guardar los mejores k”)
- “Estructura de los saltitos potencia de 2” en árbol con raíz
- LCA en O(lg n) u O(1) (Usando reduccion a RMQ, o usando la estructura de los saltitos). Aplicación para calcular distancias en un árbol en O(lg n)
- Queries en árboles: Caminos, LCA, linealizar, estructura saltitos potencia de 2 (generaliza sparse table a un árbol: en el caso estático va joya), queries subarbol, Persistencia, “truquito + -” para el camino (evita HL-decomposition cuando la operación tiene inverso), Heavy-Light decomposition.
- Tablas Aditivas (Multi Dimension)
- Sparse Table (Multi Dimension)
- Binary Index Tree (Fenwick Tree) (Multi Dimension)
- Persistencia (En Segment Trees, TREAPs, Fenwicks, Stacks, etc)
Strings
- Knuth Morris Pratt (KMP), y su tablita de bordes.
- Rabin-Karp, y uso del concepto de hash en general.
- Aho-Corasick.
- Suffix Array (Algoritmo de Larsson y Sadakane), LCP
- BWT (Mismo algoritmo Suffix Array) / BWT inversa en O(N)
- Compresión de coordenadas
Programacion Dinamica
- Maxima subsecuencia creciente (En O(n^2), y su variante en O(n lg n))
- Cálculo del triangulo de pascal
- Longest common subsequence
- Edit distance mínima (La común, y permitiendo swaps adyacentes)
- Producto de matrices con costo minimo
- En una matriz yendo de una esquina a la otra solo bajando y para la derecha, maximizar la suma de las casillas visitadas.
- Knapsack (Problema de la mochila), Subset Sum
- Dar vuelto usando una cantidad minima de monedas
- Travelling Salesman Problem (y similares con subconjuntos)
- Optimal Binary Search Tree en O(n^3) y O(n^2)
- Dada una string de longitud par de {,(,[,],),} dar la minima cantidad de cambios necesarios para que quede bien parentizada.
- Dinámicas con máscaras de bits: TSP y muchas otras.
- Dinámicas con “frente”: Poner fichitas / tubitos en un tablero, y muchas otras
- DP Optimization Tricks (Chull Trick, Knuth, Divide and Conquer Optimization) http://codeforces.com/blog/entry/8219
- Josephus problem en K * ln N
Matemática y afines
- MCD (Algoritmo de euclides)
- Inverso Modular (Con euclides extendido o con Truquito elegante divulgado por Nico Álvarez)
- Teorema Chino del Resto
- Producto de matrices
- Potenciacion logaritmica
- Recurrencias lineales
- Sistemas de ecuaciones lineales
- Truquito para matrices banda. Casos especiales de interes: Bidiagonales, Tridiagonales, Adyacencias en una grilla rectangular.
- Calculo de determinantes, matriz inversa
- Operaciones aritmeticas con enteros de longitud arbitraria
- Criba de eratostenes
- Chequeos de primalidad (Trial Division,Fermat, Rabin Miller)
- Factorización (Directa por Trial Division, Algoritmo de la Rho de Pollard)
Geometria
- Vectores (Suma, Resta)
- Producto escalar
- Producto vectorial
- Area de triangulos / paralelogramos, detección de sentido de giro
- Area de poligonos
- Chequear si un punto esta en un poligono / en un segmento / en una recta / en un plano
- Teorema de Pick
- Triangulación de polígono (árbol de triángulos, demuestra que piso(n/3) guardias bastan)
- Par de puntos mas cercano en O(n lg n)
- Truquito de que v --> (w*v, w^v) es rotohomotecia de razon ||w|| que rota llevando w al eje x positivo (permite “restar angulos en enteros”, demuestra que un angulo es posible entre puntos enteros si y solo si su tangente es racional).
- Capsula convexa en O(n lg n)
- Ancho (mínimo) de conjunto (rotating calipers en la chull)
- Par de puntos mas lejano (equivale a ancho máximo: rotating calipers en la chull)
- Interseccion de dos segmentos
- Distancia entre dos segmentos
- Sweep Line (Es muy importante la idea de sweep line / sweep circle / sweep sarasa)
- Dualidad punto - línea (a,b) <--> ax + b
- Idea de eliminación de dominados / Convex hull trick
- Dualidad intervalo - punto ([A,B] -- (A,B) , complementar intervalos es reflejar por y=x (caso circular))
- Truquito de la f lineal que transforma norma 1 en norma infinito (en 2D es “rotar 45”)
- Hay O(NM) rectángulos maximales en una grilla de NxM (Implica O(T^2) para T obstáculos), y cómo enumerarlos (desde cada casilla tirar un rayito para abajo, y de donde pega, expandir para los costados. Eso pasa por todos los maximales y por algunos no maximales [y posiblemente varias veces])
Divide and conquer
- Par de puntos mas cercano en O(n lg n)
- Strassen
- Karatsuba
- Armado de fixtures (aunque hay una alternativa constructiva muy elegante y simple)
- Elemento mayoría (y solución lineal, con O(1) memoria, o alternativamente con 3/2N comparaciones)
Meet in the middle
- BFS (tipo cubo de Rubik)
- Subset sum / Mochila
Greedies
- Dar vuelto usando una cantidad minima de monedas
- Asignación de trabajos con deadline para minimizar el tiempo final.
- Optimo cubrimiento de intervalo por subintervalos.
- Codigos de Huffman (en general: “árbol binario de mínima profundidad promedio”)
- Maxima subsecuencia creciente (resolviendo “mínima partición en subsecuencias no crecientes” con un greedy, y aplicando la dualidad del teorema de Dilworth)
Backtracking
- Problema de las n reinas.
- Cubrir un tablero con fichitas.
- Sudoku.
- Problemas NP Completos: Maximum independent set, Minimum dominating set, subset sum, etc.
- Recursiones y podas de backtracking que mejoran la complejidad (Ejemplo, Max. Ind. Subset en 1.47^N)
- Board hashes (transposition tables, también re útil para BFS/Dijkstra)
Teoría de juegos
- Cálculo con DP de posiciones ganadoras y perdedoras. Propiedad Universal.
- Idea de la criba para llenar tablitas como la anterior.
- Variante de la DP donde además de quien gana se guarda la cantidad de turnos que dura el juego, dado que el que gana trata de ganar rápido y el que pierde de perder lento.
- Juegos combinatorios imparciales: Sumar de juegos.
- Nim. Misére Nim.
- Grundy Numbers, cálculo de los grundy numbers en tiempo lineal en el grafo, con DP. Cálculo del Grundy Number de una suma de juegos (el xor de los grundies).
- Algoritmo minimax para juegos de suma cero de informacion perfecta.
Teoría de lenguajes
- Autómatas Finitos
- Expresiones Regulares
- Autómatas de KMP y Aho-Corasick
- Parsing Recursivo Descendente predictivo (con “prediccion artesanal”)
Popurrí
- Detección de ciclo en función (Tortuga de Floyd, Brent)