Algoritmos y estructuras de datos

Complejidad, busqueda, orden, recursion, pilas, colas, arboles y grafos.

13 aulas · 8 horas de práctica · en el navegador, sin instalar nada

Temario

  1. Complejidad: contar pasos — Cuánto cuesta un algoritmo, medido en pasos y no en segundos, y por qué un bucle adentro de otro cambia todo.
  2. Búsqueda: lineal y binaria — Mirar uno por uno, o descartar la mitad en cada paso: la primera vez que O(log n) se ve.
  3. Taller — El radar — Un submarino escondido en una fila de doce casillas, encontrado con la búsqueda binaria del aula 2: un radar que solo dice de qué lado está, y la comparación contra ir probando casilla por casilla.
  4. Ordenar: de n² a n log n — Burbuja e inserción para entender qué cuesta, y merge sort para ver cómo se paga menos.
  5. Recursión: el problema adentro del problema — Caso base, paso recursivo, y por qué Fibonacci ingenuo es una bomba de tiempo.
  6. Taller — El buscador — Un buscador de texto de verdad, en chico: índice invertido, autocompletar con búsqueda binaria, ranking con merge sort, y consultas con todas las palabras.
  7. Pilas y colas — Dos estructuras que solo dejan tocar una punta, y por qué esa limitación es lo que las hace útiles.
  8. Tablas hash: por qué el diccionario es O(1) — Cómo un diccionario encuentra una clave sin buscarla, qué es una colisión, y cuánto cuesta no usarlo.
  9. Árboles binarios de búsqueda — Una estructura recursiva donde buscar es descartar la mitad, y qué pasa cuando se desbalancea.
  10. Grafos: BFS y DFS — Nodos y conexiones: el camino con menos escalas, y quién está conectado con quién.
  11. Programación dinámica: no calcular dos veces — Cuando un problema se arma con versiones más chicas de sí mismo que se repiten, recordar cada una convierte lo imposible en una tabla.
  12. Greedy y colas de prioridad — Elegir lo mejor ahora y no mirar atrás: cuándo alcanza, cuándo miente, y el heap que lo hace rápido.
  13. Taller — El GPS — Un GPS sobre un grafo de ciudades: menos escalas con BFS, menos kilómetros con Dijkstra, y un informe que muestra cuándo los dos caminos no coinciden.

Es parte de