Algoritmos y Estructuras de Datos. Repositorio de archivos C++

El archivo [aed.zip] contiene todos los archivos fuente, compactados en un solo archivo con “zip”. El archivo se puede abrir con unzip (Linux) (u otro utilitario zip-compatible).

Más abajo en esta página se listan los ejemplos por palabra clave.

apply-map.cpp
Escribir una función void apply_map(list<int> &L, map<int,int> &M, list<int> &ML) que, dada una lista L y una correspondencia M retorna por ML una lista con los resultados de aplicar M a los elementos de L. Si algún elemento de L no esta en el dominio de M, entonces el elemento correspondiente de ML no es incluido. Por ejemplo, si L = (1,2,3,4,5,6,7,1,2,3) y M= {(1,2),(2,3),(3,4),(4,5),(7,8)}, entonces, después de hacer apply_map(L,M,ML), debe quedar ML = {(2,3,4,5,8,2,3,4)}. [Tomado en el 1er parcial del 20/4/2006]. keywords: lista, correspondencia
areinverse.cpp
Dos corresponencias M1 y M2 son inversas una de la otra si tienen el mismo numero de asignaciones y para cada par de asignacion x->y en M1 existe el par y->x en M2. Escribir una funcion predicado bool areinverse(map<int,int> &M1,map<int,int> &M2); que determina si las correspondencias M1, M2 son una la inversa de la otra o no. [Tomado en Primer Parcial 17-SET-2009]. keywords: correspondencia, lista
ascendente.cpp
Escribir una función int ascendente1 (list <int> &L, list<list<int> > &LL) que, dada una lista L, genera una lista de listas LL de tal forma de que cada sublista es ascendente. [Tomado en el Parcial 1 20-ABR-2006].

Escribir una función int ascendente2 (list <int> &L, vector < list<int> > &VL) que, dada una lista L, genera un vector de listas VL de tal forma de que cada sublista es ascendente. [Tomado en Examen Final 29-JUL-2004]. keywords: lista

bin2ord.cpp
bin2ord: Escribir una funcion void bin2ord(btree<int> &B, tree<int> &T); que dado un AB B de enteros POSITIVOS lo convierte a un AOO con la siguiente convencion. En caso de que uno de los nodos del AB tenga uno solo de los hijos reemplazamos el valor por un valor LAMBDA (en este caso puede ser LAMBDA=-1). ord2bin: Escribir la funcion inversa void ord2bin(tree<int> &T, btree<int> &B); que dado un AOO (que supuestamente fue generado por bin2ord) lo convierte de nuevo a AB. (Deberia ser siempre B=ord2bin(bin2ord(B)) ) [Tomado 2do parcial de 2012, 2012-10-25] keywords: arbol orientado, arbol binario
btree.h
Utilitarios varios. keywords: arbol binario
cadena_pq.cpp
Determinar si una cadena z es de la forma z = x y, donde y es la cadena inversa (o espejo) de la cadena x, ignorando los espacios en blanco. Emplear una cola y una pila auxiliares. keywords: lista, pila, cola
checkmap.cpp
Dado un map<int, list<bool> > M, verificar que para todas las claves pares, la lista correspondiente tenga todos sus elementos en true o bien que sea vacia. Si el map no tiene elementos, la salida debe ser true. [Tomado en primer parcial de lab 2011-09-17]. keywords: correspondencia, lista
chunk-revert.cpp
Escribir una función void chunk_revert(list<int> &L,int n); que dada una lista L y un entero n, invierte los elementos de la lista tomados de a n. Si la longitud de la lista no es múltiplo de n entonces se invierte el resto también. Por ejemplo, si L={1,3,2,5,4,6,2,7} entonces después de hacer chunk_revert(L,3) debe quedar L={2,3,1,6,4,5,7,2}. Restricciones: Usar a lo sumo una estructura auxiliar. (En tal caso debe ser lista, pila o cola). [Tomado en el 1er parcial 21/4/2005]. keywords: lista
circulo.cpp
Coloquemos n números enteros positivos alrededor de una circunferencia inicial. Construyamos ahora sucesivas circunferencias concéntricas hacia el exterior, de igual cantidad de elementos, los cuales son obtenidos restando (en valor absoluto) pares consecutivos de la última circunferencia exterior. Entonces, dada una lista L = [ x_0, x_1, ..., x_{n-1} ] de n números enteros que representan los valores iniciales alrededor de la circunferencia inicial, escribir una función int circulo(list<int> &L); que ejecuta esta tarea y devuelva además el número de circunferencias iteradas p [Tomado en el 1er parcial del 21/4/2005]. keywords: lista
compacta.cpp
Escribir una función void compacta(list<int> &L,stack<int> &S); que toma un elemento entero n de S y, si es positivo, saca n elementos de L y los reemplaza por su suma. Esto ocurre con todos los elementos de S hasta que se acaben, o bien se acaben los elementos de L. [Tomado en el primer parcial del cursado 2010, 2010-09-14.] keywords: lista, correspondencia
compbtree.cpp
Se define una relación de orden entre árboles binarios de enteros de la siguiente forma: A<B si a<b, o bien (a=b y Ai < Bi), o bien (a=b y Ai=Bi y Ad<Bd), donde a, b son las raíces y Ai, Ad, Bi, Bd son los subárboles izquierdos y derechos de A y B. Consigna: Escribir una función bool es_menor(tree<int> &A,tree<int> &B) que retorna verdadero si A < B. [Tomado en el 2do parcial 26/5/2005]. keywords: arbol binario
concatena.cpp
Escriba procedimientos para concatenanar: a) dos listas L1 y L2 usando insert; b) un vector VL de n listas usando insert; c) una lista LL de n sublistas usando insert “básico”; d) una lista LL de n sublistas usando una opción de insert; e) una lista LL de n sublistas usando splice. keywords: lista
concatmap.cpp
Escribir una función void concat_map(map<int,list<int> >& M, list<int>& L); tal que reemplaza los elementos de L por su imagen en M. Si un elemento de L no es clave de M entonces se asume que su imagen es la lista vacía. [Tomado en el primer parcial del cursado 2010, 2010-09-14.] keywords: lista, correspondencia
conjunto1.cpp
Diversas operaciones con conjuntos: purge : purga elementos repetidos de una lista usando un conjunto como estructura auxiliar y con una implementacion tal que sea O (n). set_intersection : interseccion de conjuntos; prints : imprime los elementos de un conjunto. Keywords: conjunto, lista
conjunto2.cpp
Diversas operaciones con conjuntos: disjuntos: verifica si una serie de conjuntos son disjuntos entre si. cubre_todo: verifica si un dado conjunto W cubre incluye a toda una serie de conjuntos Si. todos_pares: verifica si todos los elementos de un conjunto son pares. Keywords: conjunto, lista
conjunto3.cpp
Diversas operaciones con conjuntos: flat: Escribir una funcion predicado bool flat(vector< set<int> > &sw, int n); que retorna verdadero si cada par de enteros (j,k) con 0<=j,k<n esta contenido en al menos uno de los conjunto en sw. es-neg: Escribir una funcion predicado bool es_neg(set<int> &A,set<int> &B); que retorna verdadero si el conjunto B contiene exactamente los mismos elementos que A, pero cambiados de signo. en-todos: Escribir una funcion predicado bool en_todos(vector< set<int> > &v) que retorna verdadero si existe al menos un elemento que pertenece a todos los conjuntos v[j]. mediana: Escribir una funcion int mediana(list<int> &L) que retorna la mediana de los valores contenidos en la lista L. [Tomados en el 3er parcial del 24-jun-2004] Keywords: conjunto
connected.cpp
Dado un grafo como map<int,set<int>> G encontrar los subconjuntos del mismo list<set<int>> D que estan desconectados. Por ejemplo, si G={1->{2},2->{1},3->{4},4->{3}}, entonces debe retornar D=({1,2},{3,4}). La signatura de la funcion a implementar es void connected(map<int,set<int>> &G, list<set<int>> &D);

[Tomado en el 3er parcial 2008-11-20]. keywords: conjunto

contenido.cpp
Escribir una función predicado bool contenido(btree<int> &A, btree<int> &B); que retorna verdadero si la estructura del árbol binario A esta “contenido” dentro de la de B y las etiquetas correspondientes de A son menores que las de B+. [Tomado en el examen 2do parcial del 27/5/2004]. keywords: arbol binario
contnprof.cpp
Escribir una función int cant_nodos_prof(btree<int> &A, int prof); que retorna el número de nodos de una árbol binario A que están a profundidad prof o mayor.
countif.cpp
Escribir una función int count_if(tree<int> &T,bool (*pred)(int x)); que retorna el número de nodos del árbol T que satisfacen el predicado pred. Por ejemplo, si T=(1 2 (3 5 7 6) 4), entonces count_if(T,odd) debe retornar 4. Escribir el predicado bool odd(int x) que determina si un entero es impar.

Escribir una función void list_if(tree<int> &T,list<int> &L,bool (*pred)(int x)); que retorna en L la lista de valores nodales en orden previo de un árbol ordenado orientado T que satisfacen el predicado pred. Por ejemplo, si T=(1 (-2 7 (8 -7) (3 -5 -6))), entonces después de list_if(T,L,positive), debe quedar L={1,7,8,3}. Escribir el predicado bool positive(int x) que determina si un entero es mayor que 0. [Tomado en el 2do parcial 26/5/2005]. keywords: arbol orientado

countlev.cpp
Escribir una funcion void count_level(tree<int> &T, int l), que cuenta cuantos nodos hay en el nivel l del arbol T. [Tomado en el TPL2 2013-10-12]. keywords: arbol orientado
cum_sum_cola.cpp
Escribir una función void cum_sum_cola (queue<int> &Q) que modifica a la cola Q dejando la suma acumulada de sus elementos, es decir, si los elementos de Q antes de llamar a cum_sum_cola(Q) son Q = (a_0,a_1,...,a_{n-1}), entonces después de llamar a cum_sum_cola(Q) debe quedar Q = (a_0, a_0 a_1, ..., a_0 + a_1 + ... + a_n)+. [Tomado en el Primer Parcial 27-ABR-2004] keywords: cola
cum_sum_pila.cpp
Escribir una función void cum_sum_pila (queue<int> &S) que modifica a la pila S dejando la suma acumulada de sus elementos, es decir, si los elementos de S antes de llamar a cum_sum_pila(S) son S = (a_0,a_1,...,a_{n-1}), entonces después de llamar a cum_sum_pila(S) debe quedar S = (a_0, a_0 a_1, ..., a_0 + a_1 + ... + a_n)+. [Tomado en el Primer Parcial 27-ABR-2004] keywords: pila
cumsum-ab.cpp
Igual a cumsum.cpp pero ahora para AB. El cumsum(v) de un vector v es la suma acumulada, es decir en la posicion v[j] debe quedar la suma de los elementos de v[0..j]. Para un arbol lo podemos extender diciendo que en cada nodo del arbol queda la suma de los valores de los nodos de su subarbol ANTES de la operacion. keywords: arbol binario
cumsum.cpp
El cumsum(v) de un vector v es la suma acumulada, es decir en la posicion v[j] debe quedar la suma de los elementos de v[0..j]. Para un arbol lo podemos extender diciendo que en cada nodo del arbol queda la suma de los valores de los nodos de su subarbol ANTES de la operacion. Por ejemplo si T=(1 (2 (3 4 5 6)))) entonces despues de cumsum(T) debe quedar T=(21 (2 (18 4 5 6)))). La version hacia abajo corresponde a que en cada camino n0,n1,...,nk queden los valores cumsum[*n0,*n1,...,*nk]. keywords: arbol orientado
cutoffmap.cpp
Implementar una función void cutoff_map(map<int, list<int> > &M,int p,int q); que elimina todas las claves que NO estan en el rango [p,q). En las asignaciones que quedan tambien debe eliminar los elementos de la lista que no estan en el rango. Si la lista queda vacia entonces la asignacion debe ser eliminada. [Tomado en el primer parcial del cursado 2010, 2010-09-14.] keywords: lista, correspondencia
cyclic.cpp
Dada una correspondecia M y un elemento x0, podemos generar una secuencia (x0,x1,x2,...) de la forma x_{k1=M(xk)+. La secuencia se detiene cuando uno de los valores x_k generados no pertenece a las claves de M. En ese caso la secuencia generada es finita. Por otra parte, puede ocurrir que un elemento de la secuencia se repita, es decir x_{km=x_k+ con m>0. Es obvio que, a partir de alli la secuencia se va a repetir indefinidamente. Consigna: escribir una Escribir una funcion void cyclic(map<int,int> &M,list<int> &L); que extrae en L todas aquellas claves de M que generan una secuencia ciclica infinita. Por ejemplo, si M={(1,2),(2,5),(3,4),(4,6),(5,2)} entonces cyclic(M,L) debe retornar L=(1,2,5). [Tomado en 1er parcial 25-SEP-2008]. keywords: correspondencia, lista
dagdesc.cpp
Dados un Grafo Dirigido Aciclico (DAG) G=(V,E) y un subconjunto de vertices W\subseteq V, determinar el conjunto $D\subseteq V$ de descendientes de W, es decir d\in D si y solo si existe un camino que va de algun nodo w\in W a d.

[Tomado en el 3er parcial de 2012-11-22]. keywords: conjunto, correspondencia

decompint.cpp
A partir de un numero entero m escribir una funcion void decomp_int(int m, btree<int> &T); que construye el arbol binario T de la siguiente forma: 1) Si m=0 da el arbol vacio 2) Si m=1 contiene un solo nodo con el valor 1. 3) Si m>1 3.a) En la raiz contiene m 3.b) En los hijos izquierdo y derecho contiene los valores mr=m/2 y ml=m-mr. 3.c) Propaga recursivamente la decomposicion a los nodos. Por ejemplo si m=5 entonces el arbol generado es (5 (3 (2 1 1) 1) (2 1 1)). [Tomado en el segundo parcial 2011-10-27]. keywords: arbol binario
depthif.cpp
Dados un arbol binario T encontrar la maxima profundidad de un nodo tal que satisface un predicado dado. [Tomado en el 2do parcial del 2009-10-27]. keywords: arbol binario
diffsym.cpp
Dada una lista de conjuntos de enteros list< set<int> > l escribir una función void diffsym(list< set<int> > &L, set<int> &ad) que retorna en ad el conjunto de los elementos que pertenecen a uno y sólo uno de los conjuntos de L. Por ejemplo, si L = ({1,2,3},{2,4,5},{4,6}) entonces ad debe ser {1,3,5,6}. Notar que si el número de conjuntos en l es 2 y los llamamos A y B, entonces debe retornar ad = (A-B) union (B-A). [Tomado en el 3er parcial 23/6/2005]. keywords: conjunto
elimina_valor.cpp
Escribir una función void elimina_valor(queue<int> &Q, int n);} que elimina todos las ocurrencias del valor n en la cola Q. Por ejemplo, si Q = { 1,3,5,4,2,3,7,3,5 } y n=3, después de elimina_valor(Q,3) debe quedar Q = {1,5,4,2,7,5}. Sugerencia: usar una estructura auxiliar lista o cola. Restricciones: el algoritmo debe tener un tiempo de ejecución $O(n)$, donde $n$ es el número de elementos en la cola original. [Tomado en Exámen Final 08-JUL-2004] keywords: cola
eqclass.cpp
Dado un conjunto S y una relacion de orden bool comp(int x,int y) separar S, segun sus clases de equivalencia en una lista list<set<int>> L. Signatura: void eqclass(set<int> &S, bool (*)(int x,int y),list<set<int>> &L)

[Tomado en el 3er parcial 2008-11-20]. keywords: conjunto

es_biyectiva.cpp
Escribir una función bool es_biyectiva (map <int,int> &A) que retorna true si la misma representa una función biyectiva, esto es, si la correspondencia A describe una relación uno a uno. Por ejemplo, supongamos el conjunto X = (0,1,2,3,4,5) y consideremos las correspondencias A1 = { (0,2), (1,5), (2,0), (3,3), (4,4), (5,1) } y A2 = { (0,2), (1,1), (2,0), (3,3), (4,3), (5,1) }. En el primer caso, cada elemento (de 0 a 5) tiene preimagen, por lo que es_biyectiva (A1) debe retornar true. En cambio, en el segundo caso, los elementos 4 y 5 no tienen preimagen, por lo que es_biyectiva (A2) debe retornar false. keywords: correspondencia
espermut.cpp
Una correspondencia es una permutacion si el conjunto de los elementos del dominio (las claves) es igual al del contradominio (los valores). Consigna: escribir una funcion predicado bool es_permutacion(map<int,int> &M) que retorna true si M es una permutacion y false si no lo es. [Tomado en Primer Parcial 27-SET-2007]. keywords: correspondencia
existspath.cpp
Escribir una funcion bool exists_path (map <int, list <int> > &M, int m, int n); que dado un mapa M, que representa un grafo dirigido determina si existe un camino de m a n en el grafo. [Tomado en el 1er parcial de 2014-09-18]. keywords: lista, correspondencia, cola, grafo
expand.cpp
Escribir una funcion void expand(list<int> &L,int m); que transforma los elementos de una lista L de tal forma que todos los elementos de L resulten ser menores o igual que m, pero de tal forma que su suma se mantenga inalterada. [Tomado en primer parcial 2011-09-15]. keywords: lista
gatherset.cpp
Dado una serie de conjuntos de enteros S_j, con j en [0,N_S) juntarlos entre si aquellos que tienen al menos un elemento en comun. [Tomado en el TPL3 2013-11-09]. keywords: conjunto
graphlayers.cpp
Dado un grafo vector<set<int>> G y un vertice de partida x se desea determinar la estructuras de capas de vecinos de G alrededor de x definida de la siguiente forma: la capa 0 es {x}, la capa 1 son los vecinos de x. A partir de alli la capa n>=2 esta formada por los vecinos de los nodos de la capa n-1 (es decir la adyacencia de la capa) pero que no estan en las capas anteriores (en realidad basta con verificar que no esten en las capas n-1 ni n-2 ). [Tomado en tercer parcial 22-NOV-2007]. keywords: conjunto
graphs1.cpp
Ejercicios usando conjuntos en grafos. keywords: conjunto, correspondencia
incall.cpp
Dados n conjuntos A_0, A_1, ... A_{n-1} determinar si alguno de ellos (digamos A_j ) incluye a todos los otros. Es decir A_j\subset A_k para todo k. En ese caso, retornar el indice j, si no retornar -1. int includes_all(vector< set<int> > &setv); [Tomado en tercer parcial 22-NOV-2007]. keywords: conjunto
incluido.cpp
Escribir un predicado bool incluido(set<int> &A, set<int> &B); que retorna verdadero si y solo si A esta incluido en B. [Tomado en el 3er parcial 23/6/2005]. keywords: conjunto
intercala.cpp
Escriba procedimientos para intercalar (merge): (i) dos listas ordenadas L1 y L2 en una nueva lista L; (ii) un vector VL de n listas ordenadas como nueva lista L. Notar que intercalar (merge) implica en ambos casos que la nueva lista L debe resultar también ordenada. keywords: lista
intersecmap.cpp
Implemente una función void intersect_map(map< string,list<int> > &A, map< string, list<int> > &B,map< string, list<int> > &C) que a partir de los diccionarios A y B construye un diccionario C de manera que las claves de C son la interseccion de las claves de A y B y para cada clave k en C la imagen C[k] es la interseccion de los valores en A[k] y B[k]. [Tomado en Primer Parcial 17-SET-2009]. keywords: correspondencia, lista
inverse.cpp
Dada una correspondencia M y asumiendo que es invertible o biunivoca (esto es, todos los valores del contradominio son distintos), la correspondencia `inversa' N es aquella tal que, si y=M[x], entonces x=N[y]. Por ejemplo, si M={(0,1),(1,2),(2,0)}, entonces la inversa es N={(1,0),(2,1,(0,2))}. Consigna: Escribir una función bool inverse(map<int,int> &M,map<int,int> &N) tal que, si M es invertible, entonces retorna true y N es su inversa. En caso contrario retorna falso y N es la correspondencia `vacia' (sin asignaciones) [Tomado en el 1er parcial del 20/4/2006]. keywords: lista, correspondencia
isbalanced.cpp
Un arbol binario (AB) es balanceado si 1) Es el arbol vacio o, 2) Sus subarboles derecho e izquierdo son balanceados, y sus alturas difieren a lo sumo en 1 Consigna: Escribir una funcion bool is_balanced(btree<int> &T); que determina si el arbol esta balanceado. [Tomado en el segundo parcial 2011-10-27]. keywords: arbol binario
ishamilt.cpp
Dado un grafo map<int, set<int> >G y una lista de vertices list<int> L determinar si L es un camino hamiltoniano en G. [Tomado en tercer parcial 2011-11-24]. keywords: conjunto, grafo
isindep.cpp
escribir un predicado bool is_indep(map<int, set<int> >&G,set<int>&S); que determina si S es un conjunto independiente de G. Se dice que S es un conjunto independiente de G, si para cada par de vertices de S, NO existe una arista que los une en G. [Tomado en tercer parcial 2011-11-24]. keywords: conjunto, grafo
ismapped.cpp
Dados dos conjuntos set<int> A,B y una funcion biyectiva int f(int) determinar si es B=f(A) es decir todos los elementos de B se obtienen como imagen de A aplicando f().

[Tomado en el 3er parcial de 2012-11-22]. keywords: correspondencia

ismapset.cpp
Escribir una función predicado bool is_mapped_set(set<int> &A,set<int> &B,int (*mapfun)(int)); que retorna verdadero si el conjunto B contiene los elementos de A, mapeados via la funcion mapfun. [Tomado en recuperatorio 29-NOV-2007]. keywords: conjunto
isrotation.cpp
Determinar si una correspondencia !+map<int,int> M+ es una “rotacion” es decir, una permutacion tal que cada elemento del conjunto de las claves es asignado al siguiente elemento, en cierto orden. [Tomado en primer parcial 2011-09-15]. keywords: correspondencia, lista
isshift.cpp
Dados dos grafos escribir una funcion bool is_shift(graph_t &G1,graph_t &G2,int m); que determina si G2 es un `shift' de G1, es decir la arista (x,y) esta en G1 si y solo si (xm,y+m)+ esta en G2. [Tomado en el TPL2 2013-10-12]. keywords: correspondencia
isspngtree.cpp
Dado un grafo G, y un arbol T, decimos que T "expande" a G si la raiz n de T es un vertice de G, y los caminos de T permiten llegar desde n hasta cualquier otro nodo de G. Escribir una funcion bool is_spng_tree(G,T) (por "is-spanning-tree") que determina si T expande a G. [Tomado en el 3er parcial del 2009-11-27]. keywords: conjunto, correspondencia
issublist.cpp
Escribir una funcion bool is_sublist(list<int> &L1, list<int> &L1, list<list<int>::iterator> &iters); que dadas dos listas list<int> L1,L2 determina si la lista L2 es una sublista de L1, es decir que L2 se puede obtener a partir de L1 solo eliminando algunos de sus elementos. [Tomado en primer parcial 2011-09-13]. keywords: lista
josephus.cpp
Resolución del problema de Josephus usando la clase <list> de las STL. keywords: lista
junta.cpp
Escribir una función void junta (list <int> &L, int n) que, dada una lista L, agrupa de a n elementos dejando su suma IN PLACE. Por ejemplo, si la lista L contiene L=(1,3,2,4,5,2,2,3,5,7,4,3,2,2), entonces depués de junta (L,3) debe quedar L=(6,11,10,14,4). Prestar atención a no usar posiciones inválidas después de una supresión. El algoritmo debe tener un tiempo de ejecución O (m), donde m es el número de elementos en la lista original. [Tomado en el examen final del 1/8/2002] keywords: lista
lesser.cpp
Se define una relación de orden entre AOO de enteros de la siguiente forma: A<B si (na,c0a,c1a,c2a...)<(nb,c0b,c1b,c2b...), donde na es la raiz de A, h0a el subarbol del primer hijo de A y asi siguiendo. En la expresion anterior se toma el orden lexicografico para listas y se asume que en caso de tener longitudes diferentes se completa con -infinito. keywords: arbol orientado
lexico_stack.cpp
Escribir una función void lexico_stack(int n); que genera todas las subsecuencias ordenadas de la secuencia (1..n). Por ejemplo, si n=4 debe generar (1), (12), (123), (124), (13), (134), (14) (2), (23), (234) (24), (3), (34) y (4). [Tomado en el 1er parcial del 21/4/2005]. keywords: pila
lisp2tree.cpp
Esta version delega la conversion de string a T al operator>>(istream,T)... entonces se hace generico y funciona para cualquier tipo de dato al que se le pueda hacer un cin>>d;

keywords: arbol orientado

list2tree.cpp
Escribir una funcion list2tree(tree<int> &T,list<int> &L); que dada una lista L con el orden previo de T y el tamano de sus subarboles reconstruye T. La forma de almacenar el arbol en T es la siguiente: se almacena en orden previo 2 valores enteros por cada nodo, a saber el contenido del nodo y el numero de hijos. Por ejemplo para el arbol (6 4 8 (5 4 4) 7 9) se tenemos L=(6 5 4 0 8 0 5 2 4 0 4 0 7 0 9 0). Escribir tambien la funcion inversa tree2list(tree<int> &T,list<int> &L); [Tomado en el 2do parcial de 2010, 2010-10-28] Keywords: arbol orientado
lista_cte.cpp
Dada una lista L de enteros escribir una función bool es_constante (list <int> &L) que retorna true solo si todos sus elementos son iguales. Hacerlo con (i) sólo operaciones del TAD lista y (ii) mediante una correspondencia. Escriba un procedimiento void imprime (map <int,int> &M); para imprimir una correspondencia. keywords: lista, correspondencia
listarbb.cpp
Listado de árboles binarios en diferentes ordenes. Keywords: arbol binario
listarbo.cpp
Listado de árboles orientados en diferentes ordenes. keywords: arbol orientado
listd.h
Clase de listas doblemente enlazadas con punteros. keywords: lista
map2count.cpp
Escribir una funcion void map2count(tree<int> &A,tree<int> &B); que construye un arbol B a partir de otro dado A tal que B tiene la misma estructura que A, y el valor en el nodo nB de B es la cantidad de hojas en el subarbol del nodo correspondiente nA en A.

[Tomado en el final de 2012-12-06]. keywords: arbol orientado

map2list.cpp
Escribir las funciones map2list() y list2map() de acuerdo a las siguientes especificaciones. void map2list(map<int,int> &M,list<int> &keys,list<int> &vals); dado un map M retorna las listas de claves y valores. void list2map(list<int> &keys,list<int> &vals,map<int,int> &M); dadas las listas de claves (k1,k2,k3...) y valores (v1,v2,v3...) retorna el map M con las asignaciones correspondientes {(k1,v1),(k2,v2),(k3,v3),...}. (Nota: Si hay claves repetidas, solo debe quedar la asignacion correspondiente a la ultima clave en la lista. Si hay menos valores que claves, utilizar cero como valor. Si hay mas valores que claves, ignorarlos). [Tomado en Primer Parcial 17-SET-2009]. keywords: correspondencia, lista
mapoddeven.cpp
Dada una lista de enteros L, construir el map<int,list<int>> que mapea cada elemento impar de la lista al mayor rango que sigue al elemento pero solo constituido de elementos pares, por ejemplo si L=(9,10,6,7,6,8,6,10,2,7), entonces M= [9->(10,6),7->(6,8,6,10,2)] [Tomado en el recup de laboratorio de 2012-10-17]. keywords: lista, correspondencia
mapprepost.cpp
Escribir una función void map_pre_post(tree<int> &T,list<int> &L, int (*fpre)(int),int (*fpost)(int)) que lista los valores nodales del árbol ordenado orientado T en una mezcla de orden previo y posterior, donde en orden previo se listan los valores nodales aplicandoles fpre() y en orden posterior los fpost(). Por ejemplo, si T=(1 3 (5 6 7 8)), f(x)=x y g(x)=x1000+, entonces map_pre_post(T,L,f,g) debe dar L=(1,3,1003,5,6,1006,7,1007,8,1008,1005,1001). [Tomado en el recup 30/6/2005]. keywords: arbol orientado, lista
matrices.cpp
Multiplicar cuatro matrices de números reales M1 M2 M3 M4, donde M1 tiene 10 filas y 20 columnas, M2 es de 20 por 50, M3 es de 50 por 1 y M4 es de 1 por 100. Asuma que la multiplicación de una matriz A (p,q) por otra B (q,r) requiere z = p q r operaciones escalares (que es el número de operaciones requerido por el algoritmo de multiplicación de matrices). Encuentre un orden óptimo en que se deben multiplicar las matrices para minimizar el número total de operaciones escalares. Como podria encontrarlo si hay una cantidad arbitraria de matrices de dimension arbitraria ? keywords: algoritmos
maxcota_bo.cpp
Escribir una función int maxcota (tree <int> & t, node_t n, const int & cota) que retorna el máximo de las etiquetas de un árbol ordenado orientado tales que son menores o iguales que la cota dada. Por ejemplo, si las etiquetas del árbol A son (1,3,7,4,2,10,13) y cota=8, entonces maxcota (raiz (A), A, 8) debe retornar 7. keywords: arbol orientado
maxshare.cpp
Dado una serie de conjuntos de enteros S_j, con j en [0,N_S) y otro conjunto W encontrar aquel S_k cuya interseccion con W tiene el maximo tamano. [Tomado en el TPL3 2013-11-09]. keywords: conjunto
mergemap.cpp
Dadas dos correspondencias A y B, que asocian enteros con listas ordenada de enteros, escribir una funcion void merge_map(map<int,list<int>> &A, map<int,list<int>> &B, map<int,list<int>> &C) que devuelve en C una correspondencia que asigna al elemento x la fusion ordenada de las dos listas A[x] y B[x]. Si x no es clave de A, entonces C[x] debe ser B[x] y viceversa. Por ejemplo: si M={(1,2),(2,5),(3,4),(4,6),(5,2)} entonces cyclic(M,L) debe dejar L=(1,2,5). [Tomado en 1er parcial 25-SEP-2008]. keywords: correspondencia, lista
mkmirror.cpp
Escribir una funcion void make_mirror(tree<int> &T); que convierte in-place al arbol T en su espejo. [Tomado en segundo parcial 2011-10-27]. keywords: arbol orientado
nilpot.cpp
Dada una correspondencia M tal que el conjunto de sus valores es igual al conjunto de sus claves, encontrar el índice nilpotente, de la misma, es decir el número de veces n que hay que componerla consigo misma hasta llegar a la identidad, es decir M^n = I. Consigna: Escribir una función int nilpot(map<int,int> &M); que dada una correspondencia M retorna el mínimo entero n tal que M^n=I. [Tomado en el 1er parcial 21/4/2005]. keywords: correspondencia
nullsum.cpp
Escribir una funcion bool nullsum(list<int> &L, list<int> &L2); que dada una lista L, determina si hay un rango de iteradores no vacio [p,q) tal que su suma sea 0. Adicionalmente: escribir una funcion void nullsum_filt(map<int,list<int>> &M, map<int,list<int>> &M2); que extrae de todos los pares de asignacion (k,L) para los cuales L tiene un rango de suma zero, e inserta en M2 la asignacion (k,L') donde L' es el rango de L que tiene suma 0. [Tomado en el parcial de laboratorio de 2012-10-06]. keywords: lista, correspondencia
odd2even.cpp
Dada una lista L, escribir una funcion #void odd2even(list<int>+ &L,map<int,list<int>> &M); que mapea cada elemento impar de L a la siguiente subsecuencia de elementos pares. [Tomado en el TPL2 2013-10-12]. keywords: correspondencia, lista
open_hash_set.cpp
Diccionarios con tablas de dispersion abierta: dado el archivo de cabecera hash_set.h, escriba el correspondiente archivo open_hash_set.cpp con la implementación de las funciones indicadas a continuación, (i) Sencillas: erase (iterator_t p), clear (), size (); (ii) Más elaboradas: insert (const key_t & x); find (const key_t & x); erase (const key_t & x). Keywords: conjunto, diccionario
orden_nivel.cpp
El listado en orden de nivel de los nodos de un árbol lista primero la raiz, luego todos los nodos de profundidad 1, después todos los de profundidad 2, y asi sucesivamente. Los nodos que estén en la misma profundidad se listan en orden de izquierda a derecha. Escribir una función void orden_de_nivel (tree <int> &t) para listar los nodos de un árbol en orden de nivel. keywords: arbol orientado
ordenag.cpp
Escribir una función void ordenag (list <int> &l, int m) que, dada una lista l, va ordenando sus elementos de a grupos de m elementos. Por ejemplo si m=5, entonces ordenag ordena los primeros 5 elementos entre si, despues los siguientes 5 elementos, y asi siguiendo. Si la longitud n de la lista no es un múltiplo de m, entonces los últimos n mod m elementos también deben ser ordenados entre si. Por ejemplo, si l = (10 1 15 7 2 19 15 16 11 15 9 13 3 7 6 12 1), entonces después de ordenag (5) debemos tener l = (1 2 7 10 15 11 15 15 16 19 3 6 7 9 13 1 12). [Tomado en el examen final del 5-Dic-2002]. keywords: lista
ordnodo.cpp
Escribir una función predicado bool ordnodo(tree<int> &A); que verifica si cada secuencia de hermanos del subárbol del nodo n (perteneciente al árbol ordenado orientado A están ordenadas entre sí, de izquierda a derecha. Por ejemplo, para el árbol (3 5 (6 1 3) (7 4 5)) debería retornar true, mientras que para (3 9 (6 1 3) (7 4 2)) debería retornar false, ya que las secuencias de hermanos (9 6 7) y (4 2) NO están ordenados. Se sugiere el siguiente algoritmo: para un dado nodo retornar false si: 1) sus hijos no estan ordenados o 2) algunos de sus hijos contiene en su subárbol una secuencia de hermanos no ordenada. (recursividad). Caso contrario retorna verdadero. [Tomado en el final del 28/7/2005]. keywords: arbol orientado
parc120140918.cpp
stack-sep: Dada una pila S, escribir una funcion que deja en el tope los elementos pares y en el fondo los impares. El algoritmo debe ser estable es decir que los pares deben estar en el mismo orden entre si y los impares tambien. exists-path: Dado un mapa M que representa un grafo dirigido, y dos nodos m, n determinar si existe un camino que va del vertice m al n. extractm: Dada una lista L, y un entero m, escribir una funcion void extractm(list<int> &L,int m,list<int> &Lm); que genere una lista Lm con todos los elementos que aparecen exactamente m veces en L. [Tomado en el 1er parcial de 2014-09-18]. keywords: lista, correspondencia
parcord.cpp
Recordemos que un árbol es parcialmente ordenado si dados dos nodos m, n tal que m es hijo de n, entonces el valor de m es mayor o igual al de n. Consigna: Escribir un predicado bool es_parcialmente_ordenado(tree<int> &T,bool (*comp)(int,int), que verifica si el árbol ordenado orientado T es parcialmente ordenado con respecto a la función de comparación comp(). [Tomado en el examen final 7/7/2005]. keywords: arbol orientado
parent.cpp
Control de paréntesis en una expresión algebraica usando TAD-PILA de caracteres. Por parentización en una expresión algebraica consideramos únicamente los simbolos: paréntisis, corchetes y llaves. keywords: pila
parimpa.cpp
Escribir una función void encolar_trabajo (queue <int> &par, queue <int> &impar, int job) que, dado un código de trabajo n lo pone o bien en la cola par, o bien en la cola impar, dependiendo del número job. Escribir una función int siguiente_trabajo (queue <int> &par, queue <int> &impar) que obtiene el siguiente trabajo a procesar, dando mayor prioridad a la cola par. keywords: cola
particiona.cpp
Usando las operaciones del TAD lista, escribir una función void particiona (list<int> &L, int a) la cual, dada una lista de enteros L, reemplace aquellos que son mayores que a por una sucesión de elementos menores o iguales que a pero manteniendo la suma total constante. [Ejercicio tomado en el Exámen Final del 05/07/01] keywords: lista
print_back.cpp
Escriba una función void print_back (list<int> & L, list <int> :: iterator p) que, en forma recursiva, imprima una lista en sentido inverso, es decir, desde el final al principio de la lista. Se le da como dato el procedimiento a la primera posición de la lista. [Ejercicio 3 del final del 14/02/2002] keywords: lista
propsubset.cpp
Dada una lista de conjuntos list< set<int> > L, escribir una función predicado bool proper_subset(list< set<int> > &L), que determina si los conjuntos de la lista L son subconjuntos propios en forma consecutiva. Es decir, si L = (A_0, A_1, ...., A_{n-1}), determinar si A_j es subconjunto propio de A_{j1+, para j=0,...,n-2. [Tomado en el examen final 7/7/2005]. keywords: conjunto
ralea.cpp
Usando las operaciones del TAD lista, escribir una función void random_shuffle (list <int> &L) que, dada una lista de enteros L, reordena sus elementos en forma aleatoria. Se sugiere el siguiente algoritmo: usando una lista auxiliar Q se van generando números enteros desde 0 a length (L) - 1. Se extrae el elemento j-ésimo de l y se inserta en Q. Finalmente, se vuelven a pasar todos los elementos de la cola Q a la lista L. [Ejercicio tomado en el Exámen Final del 05/07/01] keywords: lista
reemplaza.cpp
Dada una lista de enteros L y dos listas SEQ y REEMP escribir una función void reemplaza (list<int> &L, list<int> &SEQ, list<int> &REEMP) que busca todas las secuencias de SEQ en L y las reemplaza por REEMP. Por ejemplo, si L=(1 2 3 4 5 1 2 3 4 5 1 2 3 4 5), SEQ=(4 5 1) y REEMP=(9 7 3), entonces despues de llamar a reemplaza debe quedar L=(1 2 3 9 7 3 2 3 9 7 3 2 3 4 5). Este procedimiento tiene un efecto equivalente a la función reemplazar de los editores de texto. [Tomado el 1er parcial, 16 abril 2002] keywords: lista
refina.cpp
(a) Escriba una función void refina (list<double> &L, double delta) tal que dada una lista inicial de reales clasificados de menor a mayor L, refina inserta elementos entre los de L, de tal modo que la diferencia máxima entre elementos de la lista final sea menor o igual que delta; (b) Escriba una función void desrefina (list<double> &L, double delta) tal que dada una lista inicial de reales clasificados de menor a mayor L, desrefina suprime elementos de L, de tal modo que la diferencia minima entre elementos de la lista final sea mayor o igual que delta. keywords: lista
rejunta.cpp
Usando las operaciones del TAD lista, escribir una función void rejunta (list<int> &L, int A) que, dada una lista de enteros L, agrupe elementos de tal manera que en la lista queden solo elementos mayores o iguales que A. El algoritmo recorre la lista y, cuando encuentra un elemento menor, empieza a agrupar el elemento con los siguientes hasta llegar a A o hasta que se acabe la lista. Por ejemplo, si L=[3,4,2,4,1,4,4,3,2,2,4,1,4,1,4,4,1,4,4,2], entonces rejunta (L,10) da L=[13,12,13,10,10]. En la lista final NO deben quedar elementos menores que A salvo, eventualmente, el último. [Ejercicio tomado en el Exámen Final del 05/07/01] keywords: lista
reversedag.cpp
Dados un Grafo Dirigido Aciclico (DAG) G=(V,E) obtener el DAG G'=(V,E') tal que si (v,w)\in E entonces (w,v)\in E'. (Es decir, equivale a invertir el sentido de las flechas en el dibujo).

[Tomado en el 3er parcial de 2012-11-22]. keywords: conjunto, correspondencia

rotacion.cpp
Escribir una función void rotacion (queue <int> &C), la cual saca una cierta cantidad de enteros del frente de la cola C y los vuelve a insertar en fin de la misma, de tal manera que quede en el frente de cola un número par. Por ejemplo, si C = [1, 3, 5, 2, 4] entonces, después de rotacion (C) , debe quedar C = [2, 4, 1, 3, 5]. Ejercicio tomado en el 1er parcial, 16/04/02. keywords: cola
sccount.cpp
Cuenta la cantidad de "hijos unicos" de un arbol binario. [Tomado en el TPL3 2013-11-09]. keywords: arbol binario
set_vector_bit.h
Dado el siguiente archivo de cabecera set.h escriba el correspondiente archivo set.cpp con la implementación de las funciones indicadas a continuación: (i) Sencillas: end (), erase (iterator_t p), clear (), retrieve (iterator_t p); (ii) Más elaboradas: size (), insert (const elem_t & x), find (const elem_t & x), erase (const elem_t & x); (iii) Binarias: set_union (set &A,set &B, set &C), set_intersection (set &A,set &B,set &C), set_difference (set &A,set &B,set &C). Nota: N es la cantidad de elementos del conjunto universal, asuma que es una variable global ya definida. Keywords: conjunto
sorted_list1.cpp
Escriba procedimientos para insertar, suprimir y buscar un elemento en una lista ordenada L. Versión sin funciones genéricas (comparar con sorted_list2.cpp y sorted_list3.cpp). keywords: lista
sorted_list2.cpp
Escriba procedimientos para insertar, suprimir y buscar un elemento en una lista ordenada L. Versión únicamente con funciones genéricas (comparar con sorted_list1.cpp y sorted_list3.cpp). keywords: lista
sorted_list3.cpp
Escriba procedimientos para insertar, suprimir y buscar un elemento en una lista ordenada L. Versión mediante una clase genérica (comparar con sorted_list1.cpp y sorted_list2.cpp). keywords: lista
splitd.cpp
Dados dos enteros M y n, tales que n<M crear un arbol binario completo (ABC) T tal que: 1) La suma de las hojas es M, pero cada una de ellas es h<=n. 2) Se satisface que para cada nodo n la suma de sus dos hijos l y r es n=lr+. Ayuda: El arbol se puede construir poniendo inicialmente M en la raiz, y dividiendo cada nodo por 2 hasta obtener valores <=n. keywords: arbol binario
splitdaoo.cpp
Dados dos enteros M y n, tales que n<M crear un AOO T tal que: 1) La suma de las hojas es M, pero cada una de ellas es h<=n. 2) Se satisface que para cada nodo p la suma de sus hijos es *p. 3) Cada nodo tiene a lo sumo g hijos, con g>1 una constante dada. Ayuda: El arbol se puede construir poniendo inicialmente M en la raiz, y dividiendo el contenido *n de cada nodo en g valores aprox iguales hasta obtener valores <=n. [Tomado en el 2do parcial del 2009-10-27]. keywords: arbol orientado
submap.cpp
// Dada una correspondencia map<string,string> M, y una clave k0, se // desea extraer todos los pares de asignacion correspondientes a claves // conectadas con k0. [Tomado en primer parcial 2011-09-13]. keywords: correspondencia
task1_bb.cpp
Diversas operaciones en un Arbol Binario (AB) [se asume que sus etiquetas son números enteros positivos]: altura : calcula la altura; cta_hojas : cuenta el número de hojas; max_etiq_arbol: obtiene la máxima etiqueta de todo el árbol; max_epar_arbol: obtiene la máxima etiqueta par del árbol; max_etiq_hojas: obtiene la máxima etiqueta de solo las hojas; sum_etiq_arbol: obtiene la suma de todas las etiquetas; f_aplica: ejemplo simple de programación funcional usando, una vez por vez, las funciones f_duplica y f_mitad (ver en task1_bo.cpp las equivalentes para árbol orientado). keywords: arbol binario
task1_bo.cpp
Diversas operaciones sobre un Arbol Ordenado Orientado (AOO) [se asume que sus etiquetas son números enteros positivos]: altura : calcula la altura; cta_hojas : cuenta el número de hojas; max_etiq_arbol : obtiene la máxima etiqueta de todo el árbol; max_epar_arbol : obtiene la máxima etiqueta par del árbol; max_etiq_hojas : obtiene la máxima etiqueta de solo las hojas; sum_etiq_arbol : obtiene la suma de todas las etiquetas; f_aplica : ejemplo simple de programación funcional usando, una vez por vez, las funciones f_duplica y f_mitad (ver en task1_bb.cpp las equivalentes para árbol binario). Otras: es_camino, is_path, list_if profundidad : calcula la profundidad de un nodo. get_node_by_pre_index : busca un nodo dado su indice (en preorden). keywords: arbol orientado
task2_bb.cpp
Diversas operaciones con árboles binarios: semejante: determina si dos árboles tienen la misma estructura; espejo : determina si la estructura de un árbol es la espejada de otro; iguales : determina si dos árboles son iguales, en estructura y contenido; copiaespejo: copia un árbol en otro en forma espejada. keywords: arbol binario
task2_bo.cpp
Diversas operaciones sobre un Arbol Ordenado Orientado (AOO). todos_pares(tree<int> &A): verifica si todas las etiquetas son pares. bool algun_par(tree<int> &A);: verifica si alguna de las etiquetas es par. int nodos_n(tree<int> &A,int n); cuenta los nodos cuya etiqueta es igual a n. int nodos_mayores_que(tree<int> &A, int m); cuenta el número de nodos cuya etiqueta es mayor o igual que m. [Tomado en el 2do parcial del 27/5/2004]. keywords: arbol orientado
tpl1-2013.cpp
Escribir una funcion void split_mod(list<int> &L, int m, vector<list<int> > &VL); que dada una lista L, y un entero m divide a la lista en las sublistas de los elementos que son congruentes entre si modulo m. Es decir en VL[j] deben quedar los elementos tales que x%m==j.

Escribir una funcion predicado bool is_sublist(list<int> &L1, list<int> &L2); que determina si L2 es una sublista de L1 es decir si L2 se puede obtener de L1 solo borrando elementos de L1.

Escribir una funcion void max_sublist(list<int> &L, list<int> &subl); que dada una lista L retorna la maxima sublista contigua de L con elementos pares subl.

[Tomado en el TPL1 de 2013-08-31]. keywords: lista

tpl120150829.cpp
mochila: Escribir una funcion M=mochila(P,K); que resuelve el problema de la mochila. Dada una lista de enteros positivos !+P+ y un peso maximo !+K+ encontrar la sublista !+M+ de !+P+ que maximiza el valor (cantidad de objetos) con un peso !+<=K+.

enunosolo: Dada una lista de listas !+LL+ y una lista !+L+, determinar si cada elemento de !+L+ esta contenido en una y solo una lista de !+LL+.

ppt: Escriba una funcion int ppt(list<int> &H, int n); que reciba una lista de enteros que representan todas las elecciones previas del jugador oponente en el juego piedra-papel-tijera y devuelve la siguiente mas probable nextplay. Para ello debe buscar en su historial H todas las veces que el jugador juega la misma secuencia que en las ultimas n partidas y retornar el valor siguiente.

[Tomado en el Trabajo Practico de Laboratorio Nro 1 (TPL1) de 2015-08-29]. keywords: lista

tpl120160908.cpp
transpose: Sea un vector de listas M que almacena los coeficientes de una matriz A de m*n entradas, escribir una funcion void transpose(vector<list<int>> &M,vector<list<int> > &Mt); que retorna los coeficientes de la matriz transpuesta es decir la lista Mt[j] contiene la columna j-1.

homogeniza: Implemente una funcion void homogeniza(list<int> &C, int hmin, int hmax); que recibe una lista C de enteros ordenados en forma ascendente y la modifica de tal manera de que entre cada elemento no exista una diferencia menor a hmin ni mayor a hmax.

bool-opers: Dadas dos listas ordenadas L1 y L2, escribir una funcion void bool_opers(list<int> &Lxor, list<int> &Land, list<int> &L1, list<int> &L2);

que deja en Lxor una nueva lista ordenada con todos los elementos que esten en solo una de las dos listas originales, y en Land una nueva lista ordenada con todos los elementos que esten en ambas.

[Tomado en el Trabajo Practico de Laboratorio Nro 1 (TPL1) de 2016-09-08]. keywords: lista

tpl120170908.cpp
extract-range: Dada una lista de enteros L1 y dos iteradores en la misma p,q, extraer el rango [p,q) de L1 en la lista L2. Nota: ambos p,q pueden ser end() y no necesariamente p esta antes de q.

add-elements: Insertar cada uno de los elementos de la pila S en la lista ordenada L, la cual debe permanecer ordenada luego de la insercion. La funcion debe retornar la cantidad de numeros repetidos en la lista L luego de la insercion. Tener en cuenta que si hay mas de dos ocurrencias del mismo numero, dicho numero cuenta una unica vez en la suma de elementos repetidos.

coprimos: Escribir una funcion #bool coprimos(list<int> &L);# que retorna true si todos los elementos de L son coprimos entre si. Recordemos que dos enteros son coprimos entre si el unico entero que divide a ambos es 1.

[Tomado en el TPL1 de 2017-09-08]. keywords: lista, pila, cola

tpl1d20140830.cpp
large-even-list: Dado un vector<list<int>> &VL buscar aquella lista VL[j] que contiene la maxima cantidad de pares y retornar la sublista de pares correspondientes (en el mismo orden que estan en VL[j] ). Si hay varias listas con la maxima longitud retornar la primera.

interlaced-split Dada una lista de enteros L y un entero positivo m dividir a L en m sublistas (en un vector de listas vector< list<int> > VL ) en forma entrelazada es decir (a0,a1,a2...) van correspondientemente a las listas VL[0], VL[1], VL[m-1], VL[0], VL[1] ... Es decir, el elemento aj va a la lista VL[k] donde k=j%m y j es la posicion entera en la lista.

interlaced-join: Es la inversa de interlaced_split(). Dado un vector< list<int> > VL juntarlos en una lista L de uno a la vez. Es decir, primero los primeros elementos de VL[0], VL[1], ..., VL[m-1], despues los segundos elementos, hasta que se acaben todas las listas.

[Tomado en el TPL1 de 2014-08-30]. keywords: lista

tpl1r20150912.cpp
iscomb: Dado un vector de listas VL y una lista L, determinar si L es una combinacion de las listas de VL en alguna permutacion dada. Cada una de las VL[j] debe aparecer una y solo una vez en L.

max-sublist: Escribir una funcion que recibe una lista de enteros y encuentra y retorna la sublista consecutiva que obtenga la mayor suma entre todos sus elementos.

mergesort: Programar una funcion void mergesort(list<int> &L); que ordane una lista L desordenada y la ordene en forma ascendente mediante una estrategia recursiva.

[Tomado en el Recup Trabajo Practico de Laboratorio Nro 1 (TPL1R) de 2015-09-12]. keywords: lista

tpl1rec-2013.cpp
mergekw: Dado un vector de listas ordenadas hacer una fusion K-way, es decir juntar todas las listas en una sola, tambien ordenada. El algoritmo K-way consiste en recorrer los primeros elementos de las listas (atencion que algunas pueden estar vacias), tomar el menor e insertarlo al fin de la lista L Esto se realiza hasta que todas las listas esten vacias. El algoritmo es similar a la fusion de dos listas, pero generalizado a K listas.

splitlist: Dado un vector de listas VL1 y un entero M devolver otro vector de listas VL2 donde las listas tienen a lo sumo M elementos.

join-list: Dado un vector de listas VL1 escribir una funcion que va juntando listas de VL1 hasta que todas tengan longitud >=M.

[Tomado en el Recup TPL1 de 2013-09-19]. keywords: lista

tpl22013.cpp
Contiene count-level, odd2even, y is_shift. [Tomado en el TPL2 2013-10-12]. keywords: correspondencia, lista, arbol orientado
tpl220161013.cpp
unordered-equal: Escribir una funcion bool que reciba dos Arboles Ordenados Orientados (AOO) y retorne true si son desordenadmente iguales. Es decir si se pueden transformar uno en el otro conpermutaciones en la lista de hermanos de cada nod.

hay-camino: Un viajante quiere viajar desde una ciudad a otra siguiendo algun camino del grafo conexo de rutas M. Lamentablemente se tiene la informacion de que en algunas ciudades hay piquetes y es imposible pasar por ellas. Para determinar si es posible realizar el viaje se debe implementar una funcion, que recibe el mapa de rutas disponibles (cada arista del grafo representa una ruta directa disponible entre las ciudades de los vortices que conecta), y la lista de ciudades con piquetes. La funcion debe retornar verdadero si existe alguna ruta que comience en la ciudad cini y finalice en cend sin pasar por ninguna de las ciudades con piquetes.

enhance-html: Los desarrolladores de un sitio web desean resaltar los links que aparecen dentro de cada pagina del sitio. Para ello es necesario que cada link (tag <a> en HTML) se encuentre dentro de un tag <strong>. Para resolver este problema ya contamos con un parser del codigo HTML que lo representa en un tree<string>. Escribir una funcion que recorre dicho arbol y si encuentra una hoja con tag a le agrega un padre strong.

[Tomado en el Trabajo Practico de Laboratorio Nro 2 (TPL2) de 2016-10-13]. keywords: correspondencia, arbol orientado

tpl220171012.cpp
prom-nivel: Dado un arbol T, calcular una lista de reales P, donde el elemento l de la lista sea el promedio de los nodos del arbol de nivel l.

es-circuito: Dado un grafo G representado por un map de nodos a lista de vecinos, y una lista de nodos L, escriba una funcion que determine si la secuencia de nodos L es un camino dentro del grafo G.

map-graph: Dado un grafo Gin y una permutacion P, encontrar el grafo Gout que resulta de permutar los vertices de Gin por la pertmutacion P, es decir si la arista (j,k) esta en Gin, entonces la arista (P[j],P[k]) debe estar en Gout.

[Tomado en el TPL2 de 2017-10-12]. keywords: correspondencia, arbol orientado

tpl2r20141016.cpp
mkmtree: Escribir una funcion que dados dos enteros positivos m, k, construye un AOO, tal que tiene a m en la raiz y dado un nodo n los hijos de n son (*n)-j*k, mientras sean no negativos. Por ejemplo si m=10,k=3 debe retornar T=(10 (7 (4 1) 1) (4 1) 1).

has-equal-path: Dado un arbol ordenado orientado (AOO) escribir una funcion predicado que determina si contiene un camino de valores iguales que va desde la raiz a una hoja con todos elementos iguales.

pancake-sort: Dada una pila de numeros S, implementar el algoritmo de ordenamiento Pancake Sort, el cual ordena la pila solo haciendo operaciones en las cuales se invierte un rango contiguo de elementos en el tope de la pila.

count-cycles: Dado un map<int,int> &M que representa una permutacion (es decir tal que el conjunto de las claves es igual al conjunto de las imagenes) escribir una funcion que cuenta sus ciclos.

[Tomado en el Recup Trabajo Practico de Laboratorio Nro 2 (TPL2R) de 2014-10-16]. keywords: arbol orientado,cola,pila,grafo,correspondencia

tpl2r20151022.cpp
tree2count: Dado un arbol T conntruye una lista L que contiene en preorder la cantidad de nodos de cada subarbol de T. E.g. T=(3 (2 1 5) (7 8)) da L=(6 3 1 1 2 1). Decimos que T es un arbol de conteo si en los nodos tiene la cantidad de nodos de su subarbol.

count2tree: Es la inversa de tree2count, dada la lista de conteo reconstruye el arbol. No recupera los valores de los nodos del arbol sino que en los nodos quedan las conteos de hijos. E.g. L=(6 3 1 1 2 1). T=(6 (3 1 1) (2 1)).

Notemos que count2tree(tree2count(count2tree(T)))=count2tree(T). Es decir count2tree es la inversa de tree2count asumiendo que T ya es un arbol de conteo.

hasnpath: Dado un grafo G, dos vertices a,b, y un entero n>=0 determina si existe un camino (con posibles nodos repetidos) de longitud n de a a b.

key2abbrev: Dado una serie de strings keys encontrar para cada uno de ellos un prefijo unico abb lo mas corto posible. Por ejemplo (mesa metro multa) -> (me met m).

[Tomado en el Recup Trabajo Practico de Laboratorio Nro 2 (TPL2R) de 2015-10-22]. keywords: arbol orientado, grafo, correspondencia

tpl320161103.cpp
puede-simplificar: Se utiliza un arbol binario para representar una expresion matematica, donde los nodos interiores representan operadores binarios, y los nodos hoja operandos (variables o constantes). Escriba una funcion para determinar si la expresion que representa el arbol puede simplificarse extrayendo un factor comun.

prune-and-return: Implemente la funcion prune(T,v,L) que dado un arbol binario T busque el nodo cuya etiqueta sea v y retorne en L la lista en preorden de todos los nodos del subarbol correspondiente. Adicionalmente el nodo y su subarbol debe ser eliminado de T.

gather-sets: Dado un vector de conjuntos y un predicado retornar la union de todos los conjuntos que contienen al menos un elemento que satisface el predicado.

[Tomado en el Trabajo Practico de Laboratorio Nro 3 (TPL3) de 2016-11-03]. keywords: arbol binario, conjunto, programacion funcional

tpl3d20141101.cpp
bijsubset: Dado un conjunto S y una funcion de mapeo T(*f)(T) determinar el conjunto S1 de elementos x de S1 tales que no existe otro elemento z con f(x)=f(z). Es decir, para los elementos de S1 y su imagen, la relacion es biyectiva.

preimage: Dados un vector<set<int> > VX y un set<int> Y, y una funcion de mapeo T(*f)(T) encontrar el conjunto de VX[j] preimagen de Y tal que si se le aplica f a sus elementos, se obtiene Y.

is-recurrent-tree: Dado un arbol binario lleno (todos sus nodos interiores tienen los dos hijos), verificar si es un *arbol recurrente.* Un arbol binario se considera recurrente si cada uno de sus nodos interiores es la suma de sus 2 nodos hijos. Se generaliza ademas para cualquier funcion asociativa g(x,y), es decir no solo para la suma.

ordered-tree: Dado un vector de numeros enteros positivos, se debera armar un arbol binario de manera que la posicion i-esima del vector verifica si es mayor que la raiz. En caso que sea mayor, intentara insertarse en el subarbol derecho de la misma, y sino en el subarbol izquierdo. Si el hijo correspondiente esta vacio entonces lo inserta alli, si no lo compara con el elemento, y vuelve a aplicar la regla recursivamente. La definicion es similar a la de un arbol binario, pero no representa un conjunto, es decir los elementos pueden estar duplicados.

[Tomado en el Trabajo Practico de Laboratorio Nro 3 (TPL3) de 2014-11-01]. keywords: arbol binario, conjunto

tpl3r20141106.cpp
only1: Dado un vector de conjuntos VS, determinar el conjunto S1 de todos aquellos elementos que estan en uno y solo uno de ellos. Por ejemplo, si VS=[{0,1,2,3},{2,3,4,5}], entonces S1={0,1,4,5}.

included: Dada un vector de conjuntos, escribir una funcion predicado, que determina si los conjuntos del vector son subconjuntos propios en forma consecutiva. Es decir, si S_j\subset S_{j1+ para j=0,...,n-2. (Recordar que A\subset B indica inclusion propia, es decir A\subseteq B y A\neq B$.

diffh: Escribir una funcion predicado que determina si el arbol esta balanceado, es decir si para cada nodo interno del AB la diferencia de alturas de los subarboles de su hijo izquierdo y derecho difieren en a lo maximo 1.

onechild: Dado una arbol binario (AB), determinar cuantos nodos de tienen exactamente un solo hijo (single child count).

[Tomado en el Recup Trabajo Practico de Laboratorio Nro 3 (TPL3R) de 2014-11-06]. keywords: arbol binario,conjunto

tplr20161110.cpp
max_sublist_m Programar una funcion max_sublist_m(list<int> &L, int m); que reciba una lista de enteros L y un entero m tal que 0<m<=L.size(), y encuentre y retorne el valor de la mayor suma de entre todas las posibles sumas de sublistas de longitud m.

remove_max_sibling: Escribir un funcion void remove_max_sibling(tree<int>&T); que borra el mayor hijo de cada lista de hijos.

max_siblings_sum: Escriba una funcion void max_siblings_sum(tree<int>&T,list<int>&L); que reciba un AOO y retorne la lista de nodos hermanos (ordenados desde el mas izquierdo) que obtenga la mayor suma entre todas sus etiquetas.

max_valid_path: Implementar la funcion int max_valid_path(map<int,set<int>>& G, bool (*pred)(int)); que recibe un grafo no dirigido G y retorna la longitud del camino mas largo (sin repetir vertices) tal que cada uno de los nodos que lo compone satisface el predicado pred.

[Tomado en el Recup TPLs (TPLR) de 2016-11-10]. keywords: lista, arbol orientado, arbol binario, correspondencia, conjunto, programacion funcional

tplsr20141107.cpp
isomorph Dos arboles binarios #B1, B2 son isomorfos si se pueden aplicar una serie de inversiones entre los hijos derechos e izquierdos de los nodos de B2 de manera que quede un arbol semejante a B1, es decir que tiene la misma estructura.

has-sum Dado un set<int> y un entero M determinar si existe un subconjunto de S que sume exactamenet M.

find-shift Dadas dos listas L1 L2 tal que L2 es una permutacion ciclica de L1 determinar el shift.

[Tomado en el Super Recup TPL (TPLSR) de 2015-11-11]. keywords: lista, set, arbol binario

tree.h
Utilitarios varios. keywords: arbol orientado
util.cpp
Utilitarios varios. keywords: lista, cola
util.h
Utilitarios varios. keywords: lista, cola
util_btree.cpp
Utilitarios varios. keywords: arbol binario
util_btree.h
Utilitarios varios. keywords: arbol binario
util_tree.cpp
Utilitarios varios. keywords: arbol orientado
util_tree.h
Utilitarios varios. keywords: arbol orientado
verifcolor.cpp
Dado un grafo map<int, set<int> >G y una coloracion map<int,string> C determinar si C es una coloracion valida, es decir si dados dos vertices adyacentes x, y de G sus colores son diferentes. [Tomado en tercer parcial 2011-11-24]. keywords: conjunto, grafo
verifsum_bo.cpp
En un programa de diseño asistido por computadora (tipo AutoCAD) se desea mantener las piezas de un sistema (por ejemplo un auto) clasificando sus partes en la forma de un árbol, donde sus nodos interiores representan sistemas del auto (planta motriz, direccion, carroceria), sus hijos subs-sistemas y asi siguiendo hasta las hojas que son los componentes indivisibles del automovil (por ej. el tornillo de fijación del espejo retrovisor izquierdo). Se quiere mantener en cada hoja el peso (en Kilogramos) del componente, y en los nodos interiores el peso total de todos los componentes del subárbol que cuelga de ese nodo. Periódicamente se quiere verificar que efectivamente las etiquetas del árbol verifican esta propiedad, es decir que la etiqueta de los nodos interiores es la suma de las hojas del subárbol que cuelga de él. Escribir una funcion bool verif_sum (tree <int> &T, node_t n) que retorna true si el subarbol que cuelga del nodo verifica la condicion dada y false en caso contrario. Usar las primitivas del TAD Arbol Ordenado orientado. [Tomado en el segundo parcial del cursado 2002, 28/5/2002.] keywords: arbol orientado
verifsum_bo.cpp
En un programa de diseño asistido por computadora (tipo AutoCAD) se desea mantener las piezas de un sistema (por ejemplo un auto) clasificando sus partes en la forma de un árbol, donde sus nodos interiores representan sistemas del auto (planta motriz, direccion, carroceria), sus hijos subs-sistemas y asi siguiendo hasta las hojas que son los componentes indivisibles del automovil (por ej. el tornillo de fijación del espejo retrovisor izquierdo). Se quiere mantener en cada hoja el peso (en Kilogramos) del componente, y en los nodos interiores el peso total de todos los componentes del subárbol que cuelga de ese nodo. Periódicamente se quiere verificar que efectivamente las etiquetas del árbol verifican esta propiedad, es decir que la etiqueta de los nodos interiores es la suma de las hojas del subárbol que cuelga de él. Escribir una funcion bool verif_sum (tree <int> &T, node_t n) que retorna true si el subarbol que cuelga del nodo verifica la condicion dada y false en caso contrario. Usar las primitivas del TAD Arbol Ordenado orientado. [Tomado en el segundo parcial del cursado 2002, 28/5/2002.] keywords: arbol orientado

Por palabras clave:

algoritmos:
matrices.cpp
arbol binario:
bin2ord.cpp, btree.h, compbtree.cpp, contenido.cpp, cumsum-ab.cpp, decompint.cpp, depthif.cpp, isbalanced.cpp, listarbb.cpp, sccount.cpp, splitd.cpp, task1_bb.cpp, task2_bb.cpp, tpl320161103.cpp, tpl3d20141101.cpp, tpl3r20141106.cpp, tplr20161110.cpp, tplsr20141107.cpp, util_btree.cpp, util_btree.h
arbol orientado:
bin2ord.cpp, countif.cpp, countlev.cpp, cumsum.cpp, lesser.cpp, lisp2tree.cpp, list2tree.cpp, listarbo.cpp, map2count.cpp, mapprepost.cpp, maxcota_bo.cpp, mkmirror.cpp, orden_nivel.cpp, ordnodo.cpp, parcord.cpp, splitdaoo.cpp, task1_bo.cpp, task2_bo.cpp, tpl22013.cpp, tpl220161013.cpp, tpl2r20141016.cpp, tpl2r20151022.cpp, tplr20161110.cpp, tpl220171012.cpp, tree.h, util_tree.cpp, util_tree.h, verifsum_bo.cpp, verifsum_bo.cpp
cola:
cadena_pq.cpp, cum_sum_cola.cpp, elimina_valor.cpp, existspath.cpp, parimpa.cpp, rotacion.cpp, tpl120170908.cpp, tpl2r20141016.cpp, util.cpp, util.h
conjunto:
conjunto1.cpp, conjunto2.cpp, conjunto3.cpp, connected.cpp, dagdesc.cpp, diffsym.cpp, eqclass.cpp, gatherset.cpp, graphlayers.cpp, graphs1.cpp, incall.cpp, incluido.cpp, ishamilt.cpp, isindep.cpp, ismapset.cpp, isspngtree.cpp, maxshare.cpp, open_hash_set.cpp, propsubset.cpp, reversedag.cpp, set_vector_bit.h, tpl320161103.cpp, tpl3d20141101.cpp, tpl3r20141106.cpp, tplr20161110.cpp, verifcolor.cpp
correspondencia:
apply-map.cpp, areinverse.cpp, checkmap.cpp, compacta.cpp, concatmap.cpp, cutoffmap.cpp, cyclic.cpp, dagdesc.cpp, es_biyectiva.cpp, espermut.cpp, existspath.cpp, graphs1.cpp, intersecmap.cpp, inverse.cpp, ismapped.cpp, isrotation.cpp, isshift.cpp, isspngtree.cpp, lista_cte.cpp, map2list.cpp, mapoddeven.cpp, mergemap.cpp, nilpot.cpp, nullsum.cpp, odd2even.cpp, parc120140918.cpp, reversedag.cpp, submap.cpp, tpl22013.cpp, tpl220161013.cpp, tpl2r20141016.cpp, tpl2r20151022.cpp, tplr20161110.cpp, tpl220171012.cpp
diccionario:
open_hash_set.cpp
grafo:
existspath.cpp, ishamilt.cpp, isindep.cpp, tpl2r20141016.cpp, tpl2r20151022.cpp, verifcolor.cpp
lista:
apply-map.cpp, areinverse.cpp, ascendente.cpp, cadena_pq.cpp, checkmap.cpp, chunk-revert.cpp, circulo.cpp, compacta.cpp, concatena.cpp, concatmap.cpp, conjunto1.cpp, conjunto2.cpp, cutoffmap.cpp, cyclic.cpp, existspath.cpp, expand.cpp, intercala.cpp, intersecmap.cpp, inverse.cpp, isrotation.cpp, issublist.cpp, josephus.cpp, junta.cpp, lista_cte.cpp, listd.h, map2list.cpp, mapoddeven.cpp, mapprepost.cpp, mergemap.cpp, nullsum.cpp, odd2even.cpp, ordenag.cpp, parc120140918.cpp, particiona.cpp, print_back.cpp, ralea.cpp, reemplaza.cpp, refina.cpp, rejunta.cpp, sorted_list1.cpp, sorted_list2.cpp, sorted_list3.cpp, tpl1-2013.cpp, tpl120150829.cpp, tpl120160908.cpp, tpl120170908.cpp, tpl1d20140830.cpp, tpl1r20150912.cpp, tpl1rec-2013.cpp, tpl22013.cpp, tplr20161110.cpp, tplsr20141107.cpp, util.cpp, util.h
pila:
cadena_pq.cpp, cum_sum_pila.cpp, lexico_stack.cpp, parent.cpp, tpl120170908.cpp, tpl2r20141016.cpp
programacion funcional:
tpl320161103.cpp, tplr20161110.cpp
set:
tplsr20141107.cpp

(git-repo-version aed-3.1-89-g0187b6a5)
(git-repo-date Fri Oct 13 08:12:58 2017 -0300)
(processed-date Fri Oct 13 08:23:50 2017 -0300)