Tabla de contenido visto en clase y problemas propuestos para ADSW.
El código del repositorio se divide en dos paquetes principales:
es.upm.dit.adsw.g23.clases, que incluye el código utilizado durante las clases. Posiblemente haya partes incompletas o que no funcionen correctamente.es.upm.dit.adsw.g23.ejercicios, donde se incluye código incompleto.
- Introducción de la asignatura
- Contenido
- Evaluación
- Dinámica y organización de las clases
- Cuestionario de inicio de la asignatura
- Conceptos
- Algoritmo vs programa
- Problemas en clase
- Encontrar líneas duplicadas en un fichero
- Ejercicios en casa
- Instalar Java
- Instalar Eclipse
- Acceder a Hackerrank
- Conceptos: Repaso Java
- Orientación a objetos (en Java)
- Ejercicios
- Encontrar líneas duplicadas en un fichero
- Ejercicios en casa:
- Encontrar líneas duplicadas a partir de un fichero
- Arreglar la implementación de LineasRepetidasClase.
- Conceptos: Repaso Java
- Estructuras de datos básicas (arrays, listas, conjuntos, diccionarios)
- Pruebas unitarias (junit)
- Ejercicios
- Encontrar líneas duplicadas en un fichero (varias implementaciones)
- Pruebas básicas usando eclipse y junit
- Ejercicios en casa:
- Encontrar fallos y arreglar
LineasRepetidas.java - Desarrollar un método que acepte una lista de números enteros y devuelva otra lista con los mismos números, pero ordenados de mayor a menor.
- Encontrar líneas duplicadas a partir de un fichero:
- Usando sólo una lista (List)
- Usando una lista y un conjunto (Set)
- Usando una lista y un diccionario (Map)
- Analizar los programas de clase y de ejercicios para líneas repetidas:
- Intentar evaluar informalmente su eficiencia. ¿Hay alguno (claramente) mejor?, ¿por qué?
- Opcional:
- Encontrar líneas duplicadas a partir de un fichero:
- Usando sólo un conjunto
- Usar una clase común para las implementaciones anteriores (encontrar usando lista, conjunto, diccionario...)
- Usar un interfaz común para las implementaciones anteriores (encontrar usando lista, conjunto, diccionario...)
- Contar cuántas veces se repite cada línea, y devolver la palabra que más se repite (si hay empate, cualquiera de ellas)
- Usando un diccionario
- Usando dos listas
- Usando una lista
- Devolver tanto la palabra como el número de veces que se repite
- Intentar encontrar optimizaciones en todos los algoritmos implementados. ¿Hay algo que se pueda hacer con menos operaciones?
- Encontrar líneas duplicadas a partir de un fichero:
- Encontrar fallos y arreglar
- Ejercicios
- Desarrollar un método que acepte una lista de números enteros y devuelva otra lista con los mismos números, pero ordenados de mayor a menor.
- Con una nueva lista (selección)
- Sin repetición
- Con repetición
- Reutilizando la lista (selección, inserción, burbuja)
- Con una nueva lista (selección)
- Desarrollar un método que acepte una lista de números enteros y devuelva otra lista con los mismos números, pero ordenados de mayor a menor.
- Ejercicios en casa:
- Implementar los algoritmos vistos en clase
- Desarrollar pruebas generales
- Probar las implementaciones con las pruebas
- Comparar el tiempo de ejecución de las implementaciones (benchmarking)
- Implementar los algoritmos vistos en clase
- Repasar transparencias:
- Estructuras de datos
- Depuración
- Conceptos
- Complejidad (I)
- Ejercicios
- Describir qué hacen los 4 algoritmos implementados en
CodigoClase.java
- Describir qué hacen los 4 algoritmos implementados en
- Ejercicios en casa:
- Intentar estimar la complejidad de los 4 algoritmos vistos
- Conceptos
- Complejidad (II)
- Orden de complejidad
- Ejercicios
- Ejercicios en casa:
- Completar los ejercicios de tema02.EjemplosCalculo.java
Laboratorio 1.
- Conceptos
- Complejidad (III)
- Repaso de todos los conceptos
- Ejercicios
- Conceptos
- Ordenación (I)
- Bubble sort (repaso)
- Insertion sort (repaso)
- Selection sort (repaso)
- Merge sort
- Quicksort
- Ordenación (I)
- Ejercicios
- Implementar todos los algoritmos vistos
- Usar visualgo para visualizar los algoritmos de ordenación vistos en clase
- Conceptos
- Ordenación (II)
- Bubble sort (complejidad)
- Insertion sort (complejidad)
- Selection sort (complejidad)
- Quick sort (complejidad)
Merge sort(falta de tiempo)
- Ordenación (II)
- Ejercicios
- Implementar todos los algoritmos vistos
- Estimar la complejidad de los algoritmos vistos
- Razonar caso mejor, peor y medio
- Conceptos
- Ordenación (III)
- Repaso + complejidad de los ya vistos
- Quicksort (repaso rápido + complejidad)
- Diccionarios (I)
- Qué es un diccionario - la interfaz Diccionario
- Diccionario con array
- Diccionario con array ordenado
- Árboles binarios de búsqueda
- Ordenación (III)
- Ejercicios
- Implementar todos los algoritmos vistos
- Conceptos
- Diccionarios (II)
- Diccionario con array (repaso + complejidad)
- Diccionario con array ordenado (repaso + complejidad)
- Árboles binarios de búsqueda (repaso + complejidad)
- Diccionarios (II)
- Ejercicios
- Implementar todos los algoritmos vistos
- Estimar la complejidad
- De cada método (get, put, remove)
- En cada alternativa vista (array, array ordenado, árbol)
- En caso mejor, peor, medio
Laboratorio 2.
- Conceptos
- Diccionarios (III)
- Repaso
- Tablas hash
- Diccionarios (III)
- Ejercicios
- Implementar todos los algoritmos restantes (hashmap)
- Estimar la complejidad de los algoritmos restantes
- Ejercicios examen
- 2019-P1r: Pregunta 2: ListaEnlazadaOrdenada
- 2017-P1: Pregunta 2: BST en array
- 2012-F1: Ejercicio 1: Algoritmos
- 2018-F2: 1.2: Complejidad
- 2015-F2: Pregunta 1: Complejidad
- 2016-P1r: Pregunta 1: Algoritmos
- 2016-F2 Pregunta 2 P2: Algoritmos
- 20220623-P1-sol: Pregunta 1: Algoritmos
- 20210608-P1R: Pregunta 1
- 2018-F2: Pregunta 2
- 20210707-F1: Pregunta 2 : complejidad
- 20210608-F1: Pregunta 2
- Resolución de ejercicios de examen
- 2012-F1: Ejercicio 1: Algoritmos
- 2012-F1: Ejercicio 2: Ordenación
- 2019-P1r: Pregunta 2: ListaEnlazadaOrdenada
URL: https://short.upm.es/xbguu
-
HackerRank:
-
Exercism:
-
Advent of Code
- Clase:
- Grafos: definición de grafo
- Ejercicios:
- Encontrar camino entre nodos
- Modificar la definición de
Grafopara incluir pesos en las aristas
- Clase:
- Teoría: Grafos
- Camino + arcos
- Representación de grafos (muy breve)
- BFS (búsqueda en anchura) y DFS (búsqueda en profundidad) (ver código de ejemplo)
- Árbol de expansión
- Prim y Dijkstra
- Colas de prioridad
- Complejidad de Prim y Dijkstra (pincelada)
- Ejercicios:
- Teoría: Grafos
- Teoría a repasar/ver en las transparencias:
- Nomenclatura y definiciones de grafos (árboles de expansión, camino (mínimo), ciclos, grafos conexos, matriz de adyacencia)
- Interfaces/clases de grafos en las transparencias y en la práctica
- Implementación de grafos (matriz de adyacencia, lista de arcos...)
- Complejidad de Prim y Dijkstra (en detalle)
- Problemas para casa:
- Grafos:
- Implementar Prim. Probar con los ejemplos de las transparencias.
- Implementar Dijkstra. Probar con los ejemplos de las transparencias.
- Listar todos los nodos en orden de distancia desde uno dado
- Java
- Algoritmos
- Estructuras de datos
- Nodo en posición en una lista enlazada
- Borrar un Nodo
- Comparar dos listas enlazadas
- Árbol en orden
- Mejorar el código de creación de árbol (avanzado). El ejercicio consiste en hacer más rápido el método. Para ello, hay que analizar qué hacer el código, y ver qué partes son mejorables.
- Grafos: