INDICE VIDEOS PRACTICA 2025

CLASE MARTES 2025-08-12

• Ejercicio 1A - Notación asintótica y ordenamiento de funciones: A partir del 14:06, se explica que la notación asintótica (O grande) es una cota superior para el tiempo de ejecución de un algoritmo en el peor de los casos. Se resuelve un ejercicio práctico para ordenar un conjunto de funciones matemáticas según su velocidad de crecimiento, lo que ayuda a medir la eficiencia de los algoritmos.
• Ejercicio 1B - Comparación de algoritmos: A partir del 32:32, se analiza qué tamaño de problema puede resolver un algoritmo en un segundo, comparando la eficiencia de diferentes algoritmos según su complejidad (logarítmica, lineal, cuadrática, etc.).
• Ejercicio 1C - Ejercicio práctico: A partir del 51:06, se calcula el número de operaciones que un procesador puede realizar en un segundo, considerando su frecuencia de reloj. Esto se relaciona con el tamaño del problema que un algoritmo puede resolver en un período de tiempo determinado. También se determina la complejidad de un fragmento de código con un bucle anidado, concluyendo que es de orden cuadrático.
• Ejercicio 1D - Contenedores de la STL: A partir del 01:28:44, se explica el uso de los contenedores de la STL (Standard Template Library). Se detallan las diferencias entre vectores y listas, explicando cómo los primeros gestionan la memoria de forma dinámica, mientras que las segundas ofrecen una alternativa en el acceso a los elementos.

CLASE MARTES 2025-08-14

• 00:15 Determinación del tiempo de ejecución (peor, mejor y promedio): El profesor comienza por determinar el tiempo de ejecución del algoritmo. Se hace hincapié en la importancia de comentar la implementación para entender la complejidad algorítmica.
• 00:27 Definición del algoritmo: Se define el algoritmo.
• 15:26 El código del algoritmo: El instructor explica el código del algoritmo, y las implicaciones de usar diferentes estructuras de datos, como un vector.
• 36:20 La importancia de comprender la complejidad de los algoritmos: Se destaca la importancia de este concepto como una habilidad esencial para la toma de decisiones al elegir un algoritmo.
• 43:40 La importancia de comprender la propiedad de la transitividad en los algoritmos: Se explica este concepto fundamental para entender cómo funcionan los algoritmos.
• 59:00 La regla del producto en los algoritmos: El instructor explica la regla del producto, un concepto fundamental en la teoría de la probabilidad que ayuda a analizar la complejidad de los algoritmos.
• 01:03:00 Complejidad del algoritmo: Se discute la complejidad del algoritmo y cómo elegir el más adecuado para una situación específica.

CLASE MARTES 2025-08-19

• 00:00 Inicio del video y presentación del tema.
• 04:12 Comienzo de los ejercicios de Grafos y coloreo.
• 01:16:03 Se abordan los conceptos teóricos y las operaciones.
• 01:20:12 Se muestra la programación en C++.
• 01:45:32 Asignación de frecuencias.
• 01:47:45 Multiplicación de matrices.

CLASE MARTES 2025-08-21

• 01:04:33 Ejercicio 1 - Basic Sort
  • Uso de los contenedores: `list`.
  • Se explica y demuestra cómo ordenar una lista de elementos de menor a mayor utilizando una lista auxiliar. Se busca el elemento menor de la lista original, se elimina y se inserta al final de la lista auxiliar.

• 01:04:33 Ejercicio 2 - Selection Sort
  • Uso de los contenedores: `list`.
  • Se detalla un procedimiento para ordenar los elementos de una lista intercambiando el menor elemento de la lista restante con el primer elemento, de forma sucesiva.

• 01:10:58 Ejercicio 3 - Concatenar Sublistas
  • Uso de los contenedores: `list` y `splice`.
  • Se aborda la concatenación de dos sublistas utilizando el método `splice`, mostrando cómo unir una lista con otra.

• 01:10:58 Ejercicio 4 - Invertir Lista
  • Se presenta un procedimiento para invertir el orden de los elementos de una lista, sin utilizar el método `size()`.

• 01:11:53 Ejercicio 5 - Suma de Elementos con Place y debe ser O(n)
  • Uso de los contenedores: `list`.
  • Se explica cómo agrupar los últimos elementos de una lista si suman su valor y cómo debe ser el tiempo de ejecución.

• 01:11:53 Ejercicio 6 - Reemplazo de Secuencias
  • Uso de los contenedores: `list` y `stack`.
  • Se detalla un algoritmo para reemplazar una secuencia de elementos por otra, con un ejemplo práctico.

• 01:13:24 Ejercicio 7 - Ascendente
  • Se presenta cómo generar una lista de vectores de vectores de enteros, donde cada vector es una sublista ascendente.

• 01:13:24 Ejercicio 8 - Camelote
  • Se implementa un generador de vectores que retorna verdaderos si la lista es ascendente o descendente.

• 01:15:31 Ejercicio 9 - Ordena
  • Se muestra un procedimiento para ordenar una lista utilizando una función de ordenamiento específica.

• 01:15:31 Ejercicio 10 - Problema de Josefo
  • Se aborda el problema de Josefo, donde se simula la eliminación de soldados en un círculo hasta que solo queda uno.

• 01:18:27 Ejercicio 11 - Palíndromo
  • Se determina si un texto es palíndromo, es decir, si se lee igual de izquierda a derecha y de derecha a izquierda.

• 01:18:27 Ejercicio 12 - Compacta
  • Se implementa una función para eliminar elementos duplicados de una lista.

• 01:18:27 Ejercicio 13 - MaxSubList
  • Se busca la sublista de una lista de enteros que tenga la suma máxima de sus elementos.

• 01:21:40 Ejercicio 14 - Merge
  • Se combinan dos listas ordenadas en una sola lista ordenada.

• 01:21:40 Ejercicio 15 - MergeSort
  • Se implementa el algoritmo de ordenamiento MergeSort para listas.

• 01:21:40 Ejercicio 16 - Pilas y Colas
  • Uso de los contenedores: `stack`.
  • Se realizan diversas operaciones con pilas, como asignar elementos, invertir una pila, y realizar operaciones aritméticas.

• 01:31:07 Ejercicio 17 - Inverso
  • Se invierte una lista utilizando una pila auxiliar.

• 01:31:07 Ejercicio 18 - Ecuación
  • Se implementa un programa para verificar si una ecuación con paréntesis está balanceada.

• 01:31:07 Ejercicio 19 - Reparto de Cartas
  • Se simula el reparto de cartas entre varios jugadores utilizando una cola.

• 01:35:54 Ejercicio 20 - Cola de Prioridad
  • Uso de los contenedores: `priority_queue`.
  • Se implementa una cola de prioridad utilizando una lista.

CLASE MARTES 2025-08-26

• Ejercicio 2: "inverso"
  • 00:15 Se desarrolla un programa para verificar si una secuencia de caracteres es un palíndromo.
  • Contenedor utilizado: Pilas

• Ejercicio 3: "sortStack"
  • 15:35 Se resuelve un problema de ordenamiento de una lista de enteros de menor a mayor.
  • Contenedores utilizados: Deques y Pilas

• Ejercicio 4: "Burnt pancake sort"
  • 33:04 Se presenta el algoritmo "burnt pancake sort" para ordenar una pila de elementos quemados de un lado.
  • Contenedores utilizados: Vectores y Pilas

• Ejercicio 5: "sort"
  • 54:39 Se implementa un algoritmo de ordenamiento para una lista de números enteros.
  • Contenedor utilizado: Listas

• Ejercicio 6: "vuelta"
  • 01:03:07 Se resuelve un problema que implica invertir los elementos de una pila utilizando una cola auxiliar.
  • Contenedores utilizados: Colas y Pilas

• Ejercicio 7: "maximo"
  • 01:03:07 Se desarrolla un programa para encontrar el valor máximo en un `stack` limitado.
  • Contenedor utilizado: Stacks

• Ejercicio 8: "pancake_sort"
  • 01:03:07 Este ejercicio se centra en el algoritmo "pancake sort" para ordenar un `stack` de enteros.
  • Contenedor utilizado: Stacks

CLASE MARTES 2025-08-28

• 43:45 Asignar el segundo elemento desde la cima de la pila a una variable i, vaciando los dos elementos superiores de la pila.
• 44:37 Asignar el segundo elemento desde la cima de la pila a una variable i, sin modificar la pila.
• 59:16 Dado un entero n, se asigna el enésimo elemento desde la cima de la pila a la variable i, vaciando los n elementos superiores de la pila.
• 01:06:55 El programa debe determinar si una cadena de texto es de la forma z=xy, donde y es la inversa o espejo de x, ignorando los espacios. Para resolverlo, se utilizan una cola y una pila auxiliar.
• 01:21:40 El programa verifica si en una cadena de expresiones aritméticas los paréntesis están correctamente anidados.

CLASE MARTES 2025-09-02

• Ejercicio 1: Palíndromo Descripción: El primer ejercicio consiste en verificar si una cadena de texto es un palíndromo, es decir, si se lee igual de izquierda a derecha que de derecha a izquierda 00:23 Contenedores utilizados: `std::stack`, `std::vector`
• Ejercicio 2: Sort Stack Descripción: El segundo ejercicio se enfoca en ordenar una pila, ya sea de forma ascendente o descendente. A diferencia del ejercicio anterior, se utiliza una cola para el ordenamiento 46:46. Contenedores utilizados: `std::stack`, `std::queue`

CLASE MARTES 2025-09-04

• Ejercicio n.º 1 En este ejercicio se pide programar una función que encuentre una sublista con la mayor suma posible, teniendo en cuenta que algunos elementos pueden ser negativos y que en caso de que existan varias sublistas con el mismo valor se debe retornar la primera. Para resolverlo se utiliza:
  • List 00:07
  • Iteradores 13:00
  • Contenedor 15:39

• Ejercicio n.º 2 En este ejercicio se pide escribir una función que reciba una lista de listas de tareas, cada una representando las tareas de un dispositivo de una red de impresión, y que las ordene en una única pila de acuerdo a su prioridad. Para resolverlo se utiliza:

• • Pila 01:41:40
  • List 01:42:04
  • Contenedor 01:45:10

• Ejercicio n.º 3. En este ejercicio se pide escribir una función que, dada una lista de colas de enteros, reduzca cada cola hasta una longitud de n+1 elementos. Para resolverlo se utiliza:

• • Cola 01:48:47
  • Iterador 01:51:24
  • List 01:52:13

CLASE MARTES 2025-09-11

• 00:03 El video explica cómo resolver un ejercicio utilizando sublistas, considerando la restricción de que algunos elementos de la lista pueden ser negativos.
• 29:00 Se muestra cómo resolver un ejercicio utilizando una pila de prioridad. Este ejercicio considera una lista de trabajos generados por dispositivos conectados a una red, los cuales se representan con un número entero que indica su prioridad.
• 56:56 Se resuelve un ejercicio reduciendo una lista de colas a una longitud de N+1 elementos. Los primeros elementos son los de la cola original, mientras que el último elemento toma el valor de la suma de todos los elementos que estaban detrás del enésimo en la cola original.

CLASE JUEVES2025-09-16

• 41:25 Se explica la función `map2list(map<int, int> &M, list &keys, list &vals)`. Esta función extrae las claves y los valores de un `map` y los almacena en `listas` separadas.
• 02:20:00 Se presenta una segunda aproximación a la función `map2list` utilizando un bucle `while` para iterar a través del `map`.
• 02:38:00 Se desarrolla la función `areInverseMap(map<int, int> &M1, map<int, int> &M2)`, que comprueba si dos `maps` son inversos.
• 02:52:00 Se muestra cómo fusionar dos `maps`, `A` y `B`, en un tercer `map`, `C`. El video explica cómo fusionar y ordenar las `listas` de valores si una clave existe en ambos `maps`.

CLASE JUEVES2025-09-18

• 00:07 Se utiliza una estructura de datos `map<int, list>` para representar el grafo. Ejercicio 7: Se implementa una función llamada `es_camino` que verifica si una lista de vértices representa un camino válido en un grafo.
• 01:14:04 La solución devuelve una `list<list>`. Ejercicio 8: Se desarrolla una función llamada `comp_conexas` para encontrar los subconjuntos de vértices desconectados, también conocidos como componentes conexas.
• 01:14:04 Al igual que en el ejercicio anterior, el grafo se representa con un `map<int, list>`.

CLASE MARTES 2025-09-23

• 00:14 Resolución del ejercicio 8 de la guía, una función para encontrar subconjuntos de grafos que están desconectados.
• 01:06:21 Representación visual de un grafo con una herramienta externa para una mejor comprensión.
• 02:51:30 Resolución del ejercicio 9 de la guía: la función IsHamilton, que determina si un grafo es un camino hamiltoniano.
• 03:04:19 Resolución de un nuevo ejercicio, que es la misma función del ejercicio anterior, pero con un ejemplo nuevo.
• 03:22:20 Nuevo ejemplo para la función IsHamilton.

CLASE MARTES 2025-09-25

• 01:31 Parte 1: Teoría y operativos.
• 10:15 Parte 2: Programación.
• 11:08 Ejercicio 1: Se desarrolla una primera prueba con nodos, descendientes y antecesores propios.
• 33:51 Ejercicio 2: El estudiante desarrolla una segunda prueba de nodos a nivel.
• 01:06:50 *Ejercicio 3: Última prueba sobre el camino en un árbol.

CLASE CONSULTA 2025-09-29

• Listas y sus operaciones (00:09 - 02:29): Se introducen las listas y se explican operaciones como `find`, `insert`, `erase`, `begin`, y `clear`.
• Complejidad algorítmica (02:29 - 03:41): Se explica la notación Big O y la propiedad de transitividad. También se analiza la complejidad de las operaciones de lista.
• Árboles (03:41 - 08:26): Se explican los conceptos básicos de los árboles, como raíz, hijos y descendientes. Se muestra cómo dibujar un árbol AOO a partir de listas de orden anterior y posterior.
• Operaciones con árboles (08:26 - 09:47): Se muestra cómo definir descendientes y antecesores de un nodo y cómo encontrar hijos izquierdos y derechos.
• Árboles binarios de búsqueda (ABB) (40:19 - final): Se explica qué son los ABB y se muestra cómo construir uno con valores específicos.
• Manipulación de listas (00:09 - 02:29): Se muestra cómo insertar y eliminar elementos de una lista, y cómo encontrar un elemento específico.
• Análisis de complejidad (02:29 - 03:41): Se analiza la complejidad de diferentes operaciones de lista.
• Construcción de árboles (03:41 - 08:26): Se muestra cómo dibujar un árbol AOO y cómo construir un árbol binario ordenado.
• Operaciones con árboles (08:26 - 09:47): Se muestra cómo encontrar descendientes, antecesores e hijos de un nodo.

CLASE CONSULTA 2025-10-14

• Sort Child (TPL2 2024) Implementación de una función para ordenar los hijos de cada nodo de un árbol orientado. [13:06]
• 3. Make Mono Implementación de una función para modificar los valores del árbol de modo que queden ordenados monótonamente creciente en orden previo, minimizando las modificaciones. [51:00]
• Next2pos Implementación de una función para generar un mapa donde cada elemento negativo de una lista se mapea a la secuencia siguiente de elementos no negativos. [01:22:15]
• Monopath Implementación de una función para encontrar el camino monótono más largo (donde el valor del nodo es $\le$ el del hijo) desde la raíz hasta una hoja. [01:34:26]
• Replace Impar Implementación de una función para reemplazar los valores impares de los nodos de un árbol por los valores de un mapa, o por el máximo valor del mapa si la clave no existe. [02:21:21]
• Make K Grade Implementación de una función para completar un árbol con nodos de forma que todos los nodos interiores tengan al menos *K hijos*, copiando el valor del último hijo original. [03:28:15]

CLASE PRÁCTICA 2025-10-23

1. Recorridos de Árboles Binarios

• [00:00:32] Ejercicio 1: Listar Árbol Binario según Órdenes
  • Objetivo: Adaptar los recorridos clásicos (prefijo, infijo, posfijo) para la estructura de árbol binario.
  • Contenedores Usados: Btree (Árbol Binario) e Iteradores.
  • [00:01:24] Implementación del recorrido en *Orden Prefijo* (Raíz, Izquierda, Derecha).
  • [00:10:28] Implementación del recorrido en *Orden Infijo* (Izquierda, Raíz, Derecha).
  • [00:11:22] Implementación del recorrido en *Orden Posfijo* (Izquierda, Derecha, Raíz).
• [00:15:31] Consulta Teórica: Reconstrucción Unívoca del Árbol
  • Discusión sobre si el orden simétrico (infijo) es suficiente para la reconstrucción unívoca de un árbol binario.

2. Análisis de Propiedades y Estructura

• [00:17:19] Ejercicio 2A: Determinar si dos árboles tienen la misma estructura (Semejantes)
  • Objetivo: Comparar dos árboles para verificar si tienen el mismo “esqueleto” (misma disposición de nodos), independientemente de los valores internos.
  • Contenedores Usados: Btree (dos instancias) e Iteradores.
• [00:44:08] Ejercicio 2B: Determinar si un árbol es el espejo (espejado) del otro
  • Objetivo: Verificar si la estructura del árbol A es el reflejo exacto del árbol B. Se resuelve cruzando las llamadas recursivas (izquierda vs. derecha).
  • Contenedores Usados: Btree (dos instancias) e Iteradores.
• [00:56:16] Ejercicio 2D: Copiar un árbol en otro en forma espejada
  • Objetivo: Construir un nuevo árbol vacío que sea una copia del árbol fuente, pero invirtiendo la posición de los hijos (espejo) durante la inserción.
  • Contenedores Usados: Btree (dos instancias) e Iteradores.

3. Conversiones y Métricas

• [01:13:29] Ejercicio 3: Contar Nodos a partir de una Profundidad (CantNodosProf)
  • Objetivo: Escribir una función que retorne el número de nodos que se encuentran a una profundidad mayor o igual a un valor dado.
  • Contenedores Usados: Btree e Iteradores.
• [01:24:20] Ejercicio 4: Conversión de Árbol Binario a Árbol Ordenado (BinToOrd)
  • Objetivo: Transformar un Btree a un Árbol Ordenado Orientado (OrdTree). La convención es que si un nodo binario tiene solo un hijo, el nodo faltante se rellena con un valor lambda (-1) en el árbol ordenado.
  • Contenedores Usados: Btree (Origen) y OrdTree (Destino).
• [01:26:17] Ejercicio 5: Conversión Inversa (OrdToBin)
  • (Propuesto como tarea) Realizar la operación inversa al Ejercicio 4.

4. Tarea Adicional (Mencionada al Final)

• [01:49:18] Tarea Adicional: Espejo In Place con splice
  • Objetivo: Implementar la función de hacer el espejo del árbol in place (en el mismo árbol), utilizando el método splice para el intercambio de subárboles.

CLASE PRÁCTICA 2025-10-29

Estructuras de Conjuntos y Complejidad (Teoría)

• Introducción y Estructuras de Conjuntos: Se comienza la guía de trabajos prácticos N°4 y se mencionan estructuras como diccionarios, vectores de bits y árboles binarios. [00:14]
• Problemas de Conteo con Vectores de Bits: Recordatorio de cómo se visualizan conjuntos con vectores de bits. [01:34]
• Ejercicio 1A: Tiempo de Ejecución de Find en Diccionario (Tablas de Dispersión Abiertas):
• Descripción de las tablas de dispersión abiertas (cubetas como listas). [05:24]
• Peor caso de búsqueda (Worst Case): O(n). [06:56]
• Caso promedio de búsqueda (Average Case): O(1 + n/B). [08:50]
• Costo de la función hash (el O(1)). [11:22]
• Ejercicio 1B: Tiempo de Ejecución de Insert en Árbol Binario de Búsqueda (Peor Caso):
• Estructura y organización de datos en un Árbol Binario de Búsqueda (ABB). [15:39]
• Peor caso (Worst Case): Árbol degenerado (estructura lineal) resulta en O(n). [17:10]
• Dispersión Cerrada (Discusión): Diferencia con la dispersión abierta y manejo de colisiones (re-inserción, probing). [22:26]
• Funcionamiento de la eliminación (delete como marcador). [23:51]
• Búsqueda circular y detección de tabla llena. [02:02:57]
• Ejercicio 1D: Mapeo de Conjuntos con Vectores de Bits:
• Caso 1: Enteros (0-99) 33:31
• Caso 2: Enteros (n a m) 46:51

Ejercicios de Programación (Operaciones con std::set)

• Verificación y Cronograma: Transición a ejercicios de programación y revisión del calendario (TPL, Parcial). [51:10]
• Implementación de Set Union (Unión de Conjuntos): Desarrollo de la lógica utilizando iteradores para recorrer y combinar los conjuntos de manera eficiente. [59:01]
• Implementación de Set Intersection (Intersección de Conjuntos): Adaptación del código de la unión para insertar solo elementos comunes. [01:17:10]
• Implementación de Set Difference (Diferencia de Conjuntos, A \ B): Adaptación del código para incluir solo los elementos que están en A y no en B. [01:29:10]
• Uso del Iterador como Sugerencia en insert: Discusión sobre la optimización que ofrece pasar un iterador como sugerencia de posición en el método insert. [01:40:43]
• Ejercicio 2: Conjuntos Disjuntos (Disjuntos): Propuesta de lógica para verificar si todos los pares de conjuntos en un vector son disjuntos (intersección vacía). [01:48:44]
• Ejercicio 3: Diferencia Simétrica (Elementos únicos): Discusión sobre la estrategia para obtener los elementos que pertenecen a uno y solo uno de los conjuntos de una lista. [01:53:29]

CLASE PRÁCTICA 2025-11-06

Inicio y Organización de la Clase

• Introducción y asistencia [01:48]
• Discusión sobre exámenes y recuperatorios [11:28]
• Inicio de la Guía Práctica 5: Ordenamiento [12:36]

Algoritmos de Ordenamiento Lentos (N^2)

• Bubble Sort (Método de la Burbuja)
• Explicación conceptual [13:56]
• Ejemplo paso a paso con una lista 14:51]
• Discusión sobre la complejidad (O(n^2)) y su lentitud [26:13]
• Ventajas (fácil de implementar) vs. Desventajas (ineficiente) [27:25]
• Discusión sobre el peor caso (movimiento lento de elementos pequeños al inicio) [36:22]
• Condición de finalización del algoritmo (una pasada sin "swaps") [41:18]

• Insertion Sort (Ordenamiento por Inserción)
• Explicación conceptual (mantener una sublista ordenada) [42:03]
• Ejemplo paso a paso con la misma lista [43:05]
• Inserción del '2' y el '0' en la sublista ordenada [47:31]

• Selection Sort (Ordenamiento por Selección)
• Explicación conceptual (buscar el mínimo y colocarlo al inicio) [54:23]
• Ejemplo paso a paso [55:01]
• Ventaja: Garantiza que los primeros 'n' elementos están ordenados en el paso 'n' [01:01:34]

Algoritmos de Ordenamiento Rápidos (N log N)

• Quicksort (Ordenamiento Rápido)
• Introducción: Estrategia "Divide y Vencerás" [01:06:11]
• Concepto clave: Elección del Pivote [01:07:14]
• Ejemplo con una lista 01:09:16]
• Aplicación recursiva y condiciones de corte (lista vacía o de un elemento) [01:11:37]
• Discusión sobre la importancia de la elección del pivote [01:14:22]
• Análisis del peor caso (cuando la lista ya está ordenada) [01:15:22]
• Mención de Introsort (implementación híbrida en STL de C++) [01:16:38]

• Heapsort (Ordenamiento por Montículos)
• Introducción al concepto de Montículo (Heap) [01:21:04]
• Definición: Árbol binario donde el padre es siempre menor que sus hijos [01:25:27]
• Operación `makeheap`: Convertir un vector/árbol en un montículo [01:39:17]
• Demostración de `makeheap` con el ejemplo [01:42:26]
• Operación `reheap`: Re-monticulizar después de una extracción [01:35:53]
• Proceso de ordenamiento:
  • 1. Extraer la raíz (el elemento mínimo).
  • 2. Mover el último elemento a la raíz.
  • 3. Aplicar `reheap` para reordenar el montículo.
• Ejemplo completo de ordenamiento extrayendo elementos [01:46:49]
• Aclaración sobre cómo resolverlo en un parcial (dibujando los árboles) [01:51:54]

CLASE CONSULTA 2025-11-07

Consultas sobre Complejidad Algorítmica (Orden de Ejecución)

• Quicksort:
• Caso promedio (N log N) vs. Peor caso (N^) [00:03]
• Explicación de por qué el peor caso es N^2 (ej. vector ya ordenado) [00:44]
• Conjuntos con Vectores de Bits:
• Duda sobre set_union: Por qué es Orden N (mayúscula) y no N log N [01:13]
• Explicación: Se recorren todos los bits del conjunto universal (N mayúscula), haciendo una operación OR bit a bit [01:40]
• Ejemplo práctico con OR bit a bit [03:12]
• Heapsort (Montículos):
• Las dos condiciones de un montículo: Parcialmente ordenado y Parcialmente completo [06:43]
• Consecuencia de "parcialmente ordenado": El menor está en la raíz, extraer_menor es O(1) [07:31]
• Consecuencia de "parcialmente completo": reheap (remonticulizar) es Orden log N [09:01]
• Costo total de Heapsort: N veces (extraer + reheap) = N log N [09:57]
• Importancia de "parcialmente completo" para implementarlo en un vector [10:20]

Resolución de Ejercicios de Parciales Anteriores

• Ejercicio de Hash (Tabla de Dispersión Cerrada)
• Consigna: Insertar elementos con dispersión lineal y función H(x) = último dígito [13:12]
• Resolución paso a paso insertando: 29, 22, 32 (colisión), 15, 24 (colisión), 7, 11, 34 [14:19]
• Aclaración de qué es "dispersión" (la función H) vs. "redispersión" (manejo de colisiones) [15:53]
• Ejercicio de Quicksort (Parcial 2022)

Repaso de Complejidad en Árbol Binario de Búsqueda (ABB)

• Duda sobre iterador++: Aclaración de por qué es Orden N en el peor caso y log N en promedio [33:10]
• Análisis de la Tabla de Complejidad (ABB) [36:37]
• P (desreferenciar) y end(): *Orden 1 [37:12]
• insert, find, erase: Orden log N (promedio) vs. Orden N (peor caso) [38:02]
• Explicación del peor caso: Árbol degenerado en lista (ej. insertar ordenado o alternado) [38:32]
• union, intersection, difference: Orden N log N (promedio) vs. Orden N² (peor caso) [40:45]
• Aclaración: La base del logaritmo (log vs log base 2) no importa en notación de complejidad [44:03]

Repaso de Complejidad en Vectores de Bits

• Operaciones de Orden N (mayúscula):
• union, intersection, difference (binarias) [45:52]
• clear (tiene que recorrer todo el vector para poner bits en cero) [47:00]
• begin (tiene que buscar el primer bit prendido) [47:20]
• next (iterador++) (tiene que buscar el siguiente bit prendido) [48:59]
• Operaciones de Orden 1: insert, erase, find (un solo elemento) [46:32]

CLASE CONSULTA 2025-11-17

• Ejercicio de Heapsort (Ordenamiento por Montículo) Desarrollo completo del algoritmo de ordenamiento por montículo. [03:12]
• Make Heap (Construcción del Montículo) Proceso para convertir el árbol binario inicial en un montículo (Min-Heap) mediante `reHeaps` de abajo hacia arriba. [03:57]
• Proceso de Ordenamiento Extracción sucesiva del elemento mínimo de la raíz, reemplazo con el último elemento y subsiguiente `reHeap` para restablecer la propiedad de montículo. [11:43]
• Resumen del Algoritmo Pasos clave: `make Heap` inicial, seguido de un bucle de extraer, subir el último y `reHeap`. [20:37]
• Concepto de Estabilidad en Algoritmos de Ordenamiento Explicación de la estabilidad, diferencia entre relaciones de orden fuerte y débil, y cómo la estabilidad preserva el orden relativo de elementos equivalentes. [22:27]
• Ejercicio de Quicksort Desarrollo del algoritmo Quicksort, incluyendo la selección del pivote y el proceso recursivo de particionamiento. [34:33]
• Ejercicio de Codificación Huffman Procedimiento para la construcción del árbol de Huffman, agrupando sucesivamente los nodos de menor frecuencia para obtener un código óptimo. [42:26]
• Inserción en Árboles Aclaración sobre las reglas de inserción en posiciones dereferenciables (con nodo) y no dereferenciables (lambda) para Árboles Orientados y Árboles Binarios. [59:00]
• Implementación de Métodos de Lista Cómo implementar métodos de alto nivel (`push back`, `pop front`, `front`) utilizando las operaciones genéricas de la interfaz básica de listas. [01:03:33]
• Procedimiento de Mergesort (Ordenamiento por Fusión) Explicación del algoritmo basado en la división recursiva y posterior fusión ordenada de las sublistas. [01:06:27]
• Logística del Recuperatorio Consulta sobre los temas que se agregan al examen de recuperación (Mergesort y Estabilidad) y la duración del mismo. [01:10:12]