Análisis y Diseño de Algoritmos 2021-1

• Notas (actualizado 05/26)

• Software de apoyo

  • Arena de programación (DomJudge)

  • Plataforma de comunicación (Zulip)

• 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)

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

• Semestres pasados:

  • 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

• 03/03 [grabación, notas de clase]

1. Diseño y análisis de algoritmos: capítulos 1 - 5 (actualizado 03/17 - El Capítulo 5 está bastante incompleto - hay 2 secciones por ahora)

Ensuring Truth (UVa 11357) : enunciado original | arena | 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.

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.

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 como fáciles (PR-B), medios (PR-C) y difíciles (PR-D). 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 PR-B, PR-C y PR-D. 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.

A continuación se discrimina la puntuación para esta entrega:

PR-B: 5 (1 segundos)

PR-C: 10 (2 segundos)

PR-D: 20 (7 segundos)

PR-E: +10 (8 segundos)

PR-E corresponde a casos de prueba muy díficiles (en inglés evil) y su solución correcta en la arena otorga un bono de 10 puntos.

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 02/12 y 02/14

  • enunciado

  • casos de prueba

  • plantillas

• Tarea 2: para entregar 02/26 y 02/28 03/02

  • enunciado

  • casos de prueba

• Tarea 3: para entregar 03/26 y 03/28

  • enunciado

  • casos de prueba

• Tarea 4: para entregar 04/23 y 04/25 04/27

  • enunciado

  • casos de prueba

• Tarea 5: para entregar 06/04

  • enunciado

1. Bienvenida (02/02) [grabación]

   • Administrativia

   • Convenciones

   • Introducción

2. Dividir, conquistar y combinar (02/04) [grabación, notas de clase]

   • Búsqueda binaria [código]

3. Análisis asintótico (02/09) [grabación]

   • Repaso:

     • Notación O

     • Propiedades de O

   • El Teorema Maestro

   • Bisección

4. Dividir, conquistar y combinar (02/11) [grabación, notas de clase]

   • Ordenamiento con MergeSort [código]

5. Introducción a la programación dinámica (02/16) [grabación, notas de clase]

   • Propiedades de subestructura y solapamiento

   • Cálculo de números de Fibonacci [código] (por Carlos Ramírez)

6. Subarreglo de suma máxima (02/18) [grabación, notas de clase]

   • Diseño de un algoritmo con tiempo lineal con tabulación

   • Reducción del espacio de tabulación

   • Discusión de problemas de la Tarea 2 [apuntes]

7. Subsecuencia ascendente más larga (02/23) [grabación, notas de clase]

   • LIS (del inglés, longest increasing subsequnce)

   • Repaso del problema del morral

8. Problema del agente viajero (02/25) [grabación]

   • Diseño de un algoritmo con máscara de bits

   • Operaciones básicas con máscaras de bits

   • Implementación de un algoritmo con memorización

9. Repaso (03/02) [grabación, notas de clase]

   • UVa 11843 - Guessing Game [enunciado]

   • UVa 10564 - Paths through the Hourglass [enunciado]

10. Repaso (03/04) [grabación]

    • Buenas prácticas de implementación [notas de clase]

    • UVa 11584 - Partitioning by Palindrome [enunciado anotado]

11. Algoritmos voraces (03/09) [grabación]

    • Agendamiento de actividades, parte 1

12. Algoritmos voraces (03/11) [grabación]

    • Agendamiento de actividades, parte 2

    • Diseño de un algoritmo voraz

13. Cubrimiento de intervalos (03/16) [grabación, notas de clase]

    • Diseño de un algoritmo voraz

    • Implementación sin control de fallo [código]

    • Implementación con control de fallo [código]

14. Árboles de cubrimiento mínimo (03/18) [grabación]

    • Principio de optimización local

    • Algoritmo de Kruskal

    • Algoritmo de Prim

15. Más algoritmos voraces (03/23) [grabación]

    • Álgoritmos de Prim y Kruskal [notas de clase]

    • Conjuntos disyuntos [código]

    • Algoritmo de Dijkstra [notas de clase, código]

16. Más algoritmos voraces (03/25) [grabación]

    • Ideas de solución para la Tarea 3

17. Reintento (04/06) [grabación]

    • El problema de las N reinas [notas de clase, código]

18. Reintento (04/08) [grabación]

    • Subset Sum [código]

19. Reintento (04/13) [grabación, notas de clase]

    • Sudoku [código]

    • Segmentación de texto [código]

20. Reintento (04/15) [grabación, notas de clase]

    • Estrategias de solución para la tarea

21. Teoría de números computacional (04/20) [grabación, notas de clase]

    • La Criba de Eratóstenes [código]

22. Teoría de números computacional (04/22) [grabación, notas de clase]

    • Algoritmo de Euclides

23. Geometría computacional (04/27) [grabación, notas de clase]

    • Funciones básicas

24. Geometría computacional (04/29) [grabación, notas de clase]

    • Reto

25. Geometría computacional (05/11) [grabación, notas de clase]

    • Reto

26. Clases de complejidad algorítmica (05/13) [grabación, notas de clase]

    • Problemas de decisión

27. Clases de complejidad algorítmica (05/18) [grabación, notas de clase]

    • ???

28. Reducciones (05/20) [grabación, notas de clase]

    • Repaso y propieadades de reducciones