Clases teóricas

Clases iniciales:

  1. E/S + Introdución, a cargo de Agustín Santiago Gutiérrez
  2. Búsqueda binaria y ordenamiento, a cargo de Quimey Vivas
  3. Programación dinámica , a cargo de Mariano Crosetti
    • Mariano dictará un subconjunto de los siguientes temas, a definir y acorde al tiempo disponible: ¿Qué es la DP? Top Down y Bottom Up. Reconstruyendo la solución. K - ésima reconstrucción. Reducir una dimensión de memoria. Agregando una flag. Recuperando un parámetro. Dinámica en rangos. Dinámica en de máscara de bits. Dinámica en prefijos de números. Dinámica en frentes.
  4. Matemática, a cargo de Ariel Zylber
  5. Grafos, a cargo de Matías Hunicken
    • Temario tentativo: Representación de grafos, árboles, DFS/BFS, distancias mínimas (algoritmos de Dijkstra y Floyd), union-find, algoritmo de Kruskal.
  6. Estructuras de datos para programación competitiva, a cargo de Quimey Vivas
  7. Algoritmos golosos, a cargo de Pablo Zimmermann
    • Introducción a los algoritmos golosos/voraces. Cómo pensarlos. Estrategia para usarlos en competencias. Teorema de la fruta golosa y del ordenamiento de a 2 (Taravilse, Álvarez). Falsos positivos: Los Greedy que no son Greedy. Ejemplos y anécdotas personales.
  8. Strings, a cargo de Agustín Santiago Gutiérrez
    • Arreglo Z (ejemplo, buscar un string en otro). Bordes de una cadena (calculados a partir del arreglo Z, por ejemplo para encontrar sufijos o prefijos palindrómicos eficientemente). Hashing de Rabin-Karp y trucos asociados (o "cómo usar hashing para computar casi cualquier cosa de strings", como por ejemplo todos los anteriores + el resultado del algoritmo de Manacher + el suffix array de un string). Tries.

Clases avanzadas:

  1. Geometría computacional, a cargo de Melanie Sclar
    • Elementos básicos: puntos, vectores y rectas. Operaciones importantes y representación. Técnicas de barrido ("sweep line"): Par de puntos más cercano, Intersección de segmentos, Cápsula convexa (Convex Hull). Área de polígono y teorema de Pick.
  2. Dualidad punto línea y "convex hull trick", a cargo de Agustín Santiago Gutiérrez
    • "Convex hull trick" es una técnica conocida para calcular eficientemente "El máximo de varias funciones lineales", sobre un cierto valor de x. La dualidad punto línea es una forma de transformar problemas con rectas en problemas con puntos, y viceversa. Además de aprender ambas, usaremos esta última técnica para entender de dónde viene el nombre medio misterioso de "convex hull trick".
  3. Flujo máximo , a cargo de Ariel Zylber
    • En la charla se tratarán algunos de los siguientes temas: Algoritmo para flujo máximo / corte mínimo, con énfasis en cómo utilizarlo para modelar y resolver problemas de competencias. Matching máximo bipartito. Teoremas de Konig y Hall. Mínima partición/cubrimiento por caminos. Teorema de Dilworth. Flujo de costo mínimo.
  4. Matemática: Combinatoria y probabilidad, a cargo de Pablo Zimmermann
    • Introducción a la combinatoria. Formas de calcular números combinatorios. Principio de inclusión - exclusión. Nociones básicas de probabilidad en competencias. Introducción a Teoría de Juegos. Posiciones perdedoras. Nim y Misere Nim. Teorema de Sprague-Grundy.
  5. Estructuras de datos sobre árboles, a cargo de Matías Hunicken
    • Temario tentativo: heavy light decomposition, dsu on tree, centroid decomposition, link-cut tree.
  6. Suffix Automaton, a cargo de Nicolás Álvarez
    • Suffix automaton: si bien ambas cosas son importantes, la charla se enfoca más en "cómo utilizar la estructura para resolver los problemas", y no tanto en "por qué se construye así el autómata". El suffix automaton es una estructura más avanzada y complicada, continuación natural de las estructuras básicas explicadas en la charla básica de strings.