Análisis y Diseño de Algoritmos 2023-2

1. Bienvenida (07/25) [grabación]

   • Administrativia

   • Convenciones

   • Introducción

2. Notación asintótica (07/27) [grabación, apuntes, código]

   • Dividir y conquistar

   • Ordenamiento (cuadrático)

   • Uso de la notación O

3. Dividir y conquistar (08/01) [grabación]

   • Notación asintótica [apuntes]

   • Teselación de un tablero de agedrez [apuntes]

4. Dividir y conquistar (08/03) [grabación]

   • Búsqueda binaria [apuntes, código]

   • MergeSort [apuntes, código]

5. Dividir y conquistar (08/08) [grabación]

   • Teorema Maestro [apuntes]

   • MergeSort [apuntos]

6. Dividir y conquistar (08/10) [grabación, apuntes]

   • Bisección

   • UVa 12791 - Lap (IO) [enunciado, código]

7. Repaso (08/14) [grabación]

8. Parcial 1 (08/16) [enunciado, solución]

9. Programación dinámica (08/22) [grabación, apuntes]

   • Introducción

   • Cálculo eficiente de los números de Fibonacci [código]

10. Programación dinámica (08/24) [grabación, apuntes, código]

    • Subset Sum

11. Programación dinámica (08/29) [grabación, apuntes, código]

    • El problema del morral (Knapsack 0-1)

12. Programación dinámica (08/31) [grabación, apuntes, código]

    • El problema del morral (Knapsack 0-1)

    • Optimización de espacio de tabulación

13. Programación dinámica (09/05) [grabación, apuntes, código]

    • Subset Sum

14. Programación dinámica (09/07) [grabación, apuntes]

    • El algoritmo de Kadane en 1D [código]

    • El algoritmo de Kadane en 2D

15. Algoritmos voraces (09/12) [grabación, apuntes, código]

    • Selección de actividades

16. Algoritmos voraces (09/14) [grabación, apuntes, código]

    • Cubrimiento mínimo de intervalos

17. Semana diagonal (09/19)

18. Semana diagonal (09/21)

19. Algoritmos voraces (09/26) [grabación]

    • Ejercicios de la Tarea 3

20. Algoritmos voraces (09/28) [grabación, apuntes]

    • Árboles de cubrimiento mínimo

    • El algoritmo de Kruskal

    • Union-find

21. Algoritmos voraces (10/03) [grabación, apuntes]

    • Coin channge

22. Parcial 2 (10/05) [enunciado]

23. Reintento (10/10) [grabación, apuntes]

    • SEND+MORE=MONEY

    • Reinas en un tablero de ajedrez

24. Reintento (10/12) [grabación, apuntes]

    • Reinas en un tablero de ajedrez [código]

    • Segmentación de texto [código]

25. Reintento (10/17) [grabación, apuntes]

    • UVa 10950 - Bad Code [enunciado, código]

26. Reintento (10/19) [grabación, apuntes]

    • Sudoku [código]

27. Clases de complejidad (10/24) [grabación, apuntes]

    • Observaciones Tarea 4

    • Introducción a clases de complejidad

      • Lenguajes formales

      • Cardinalidad

28. Clases de complejidad (10/26) [apuntes]

    • Decidibilidad

    • Indecidibilidad

29. Clases de complejidad (10/31) [grabación, apuntes]

    • La clase P

    • Decisión vs aceptación en P

30. Clases de complejidad (11/02) [grabación, apuntes]

    • Algoritmos de verificación

    • La clase NP

    • Reducciones polinomiales

    • La clase NP-hard

    • La clase NP-complete

31. Clases de complejidad (11/07) [grabación, apuntes]

    • Repaso de NP, NP-hard y NP-complete

    • CLIQUE es NP-complete si 3CNF-SAT es NP-complete (introducción)

32. Clases de complejidad (11/09) [grabación, apuntes]

    • CLIQUE es NP-complete si 3CNF-SAT es NP-complete (demostración completa)

• Notas (actualizado 11/28)

• Texto guía

  • Capítulos 0 a 5 (actualizado 07/25)

  • Inducción (actualizado 09/29)

• Software de apoyo

  • Arena de programación (DomJudge)

  • Plataforma de comunicación (Discord)

• Otros enlaces

  • ¿Cómo usar Python en este curso?

  • Documentación de Python

  • Instalación y configuración de Python en Windows (por Carlos Ramírez)

• • 2016-1: parcial 1, parcial 2, examen final

  • 2016-2: parcial 1, parcial 2, examen final

  • 2017-1: parcial 1, parcial 2, examen final

  • 2017-2: parcial 1, parcial 2, examen final

  • 2018-1: parcial 1, parcial 2, examen final

  • 2018-2: parcial 1, parcial 2, examen final

  • 2019-1: parcial 1, parcial 2, examen final

  • 2019-2: parcial 1, parcial 2, examen final

  • 2020-1: parcial 1, parcial 2, examen final

  • 2020-2: parcial 1, parcial 2, examen final

  • 2021-1: parcial 1, parcial 2, examen final

  • 2021-2: parcial 1, parcial 2, examen final

  • 2022-1: parcial 1, parcial 2, examen final

  • 2022-2: parcial 1, parcial 2, examen final

  • 2023-1: parcial 1, parcial 2, examen final

UVa 976 - Bridge Building : enunciado | casos de prueba

Entrega 0 (10%)

Esta entrega consta de un documento que describe la naturaleza de la solución del problema. En este documento se debe reflejar qué tanto entiende del problema, cuál es su estrategia de solución y la cantidad de trabajo que ha hecho para el proyecto. En esta entrega no es necesario tener una solución del problema pero sí tener claro cómo se puede resolver.

El documento para esta entrega no tendrá más de 3 páginas y, como mínimo, deberá contener la siguiente información:

• • Especificación del problema (entrada y salida)

  • Algoritmos y estructuras de datos que usará su solución (cada decisión debe ser justificada)

  • Estrategia de solución

  • Análisis (alto nivel) de complejidad temporal y espacial de su solución

  • De ser necesario, citas bibliográficas del material consultado y que será usado en la solución del proyecto

Recuerde que el proyecto es individual.

Entrega 1 (20%)

Esta entrega consta de un único archivo fuente en el lenguaje de programación Python que debe ser aceptado en la arena como correcto en la arena disponible para el proyecto para el caso de prueba #1: Simple case.

El contenido del archivo debe contar con:

• • Un encabezado que declare de forma unívoca la autoría del código: (i) nombre del autor (estudiante quien entrega el proyecto), (ii) su código de estudiante y (iii) la frase de compromiso del código de honor del curso.

  • Documentación de cada una de las funciones usando el estándar de Python.

  • El archivo debe ser enviado, también, por BrightSpace.

Cualquier archivo entregado sin seguir los lineamientos anteriores será ignorado para efecto de la calificación del proyecto.

Entrega 2 (70%)

Esta entrega consta de dos partes: (i) solución de casos de prueba y (ii) sustentación.

Los casos de prueba están clasificados en 5 categorías. Para obtener una puntación perfecta en esta entrega es indispensable que una solución resuelva correctamente todos los casos de prueba disponibles en la arena para los casos de prueba A a E. Para que una solución sea considerada para puntuar es necesario que el archivo cumpla con las condiciones de la Entrega 1. Tenga en cuenta también que los casos de prueba deben ser resueltos por la misma solución, es decir, no es posible usar dos soluciones distintas para los casos de prueba.

Adicionalmente, para esta entrega se evaluarán durante la sustentación los siguientes requisitos no funcionales:

• • Diseño y uso clases para abstraer elementos de la solución

  • Nombres de variables, funciones/metodos, etc. en inglés

  • Elegancia del código

La sustentación de cada proyecto tomará alrededor de 10 minutos y para ello se abirará una lista de turnos. Para la sustentación es importante estar en capacidad de explicar la estrategia de solución, explicar los algoritmos utilizados (de memoria), describir las estructuras de datos utilizadas, y complejidades temporal y espacial de la solución. Una sustentación insatisfactoria del proyecto puede anular cualquier puntación otrogable por resolver satisfactoriamente casos de prueba.

La sustentación es un factor entre 0 y 1 que pondera la puntuación enumerada anteriormente: entre mejor sea la sustentación, mayor será este factor.

• Tarea 1: para entregar 08/13

  • enunciado

  • casos de prueba

  • plantillas

• Tarea 2: para entregar 09/03

  • enunciado

  • casos de prueba

• Tarea 3: para entregar 10/01

  • enunciado

  • casos de prueba

• Tarea 4: para entregar 10/22

  • enunciado

  • casos de prueba