Unidad Mérida

Temario

Sesión	Tarea
1. Pilas     * Implementando una pila con memoria estática: pila_mem_estatica.cpp     * Implementando una pila con memoria dinámica: pila_doble_apuntador.cpp     * Comprobar sintaxis de paréntesis, corchetes y llaves en  C: comprobar_sintaxis.cpp (Terminar el programa)	tarea_1.pdf
2. Colas     * Implementando una cola con memoria estática: cola_memoria_estatica.cpp     * Implementando una cola con memoria dinámica: cola_memoria_dinamica.cpp	tarea_2.pdf
3. Listas     * Implementando una lista con memoria dinámica: lista_enlazada.cpp     * Implementando una lista circular: lista_circular.cpp     * Implementando el juego de la papa se quema...: lista_circular_papa_se_quema.cpp	tarea_3.pdf
4. Lista doblemente enlazada     * Implementando una lista doblemente enlazada: lista_doble_liga.cpp (Terminar el programa)     * Implementando una lista enlazada ordenada: lista_enlazada_ordenada.cpp (Terminar el programa)	tarea_4.pdf
5. Árboles 6. Árboles Binarios de Búsqueda     * Implementando un árbol binario de búsqueda: arbol_binario_busqueda.cpp (Terminar el programa)     * Exposiciones:         a) Árboles AVL (Tarea_6: Insertar y eliminar elementos en un árbol AVL)         b) Árboles Rojo-Negro         c) Árboles AA         d) Árboles B         e) Árboles B+	tarea_5.jpg
7. Tablas hash     * Implementando una tabla hash: tabla_hash.cpp (Terminar el programa)	tarea_7.pdf
8. Grafos     Grafos no dirigidos	tarea_8.pdf
9. Algoritmos de ordenamiento	tarea_9.pdf
10. Cómputo paralelo

Calificaciones de las tareas:

Num. Ctrl.	T1	Comentarios	T2	Comentarios	T3	Comentarios	T4	Comentarios	T5	Comentarios	T6	Comentarios	T7	Comentarios	T8	Comentarios	T9	Comentarios
lt26i	9.7	T1_9	10		10	T3_3	10		0	T5_1	0	T1_17	0	T1_17	0	T1_17	0	T1_17
99991111	5	T1_1, T1_5, T1_6,T1_7,T1_8	1.5	T2_2, T1_8, T2_5, T1_16, T2_4	9	T3_10, T2_4	0	T1_17	10		2.8	T6_1	0	T1_17	0	T1_17	9	T6_1
12216300	5.5	T1_1, T1_5, T1_10, T1_11, T1_12, T1_13	7	T2_2	7.5	T3_4, T3_5, T3_6	6	T4_3, T4_2	10		7.8	T6_1	3.5	T7_4, T1_5	8.0	T6_1	9	T6_2
A07001582	6	T1_1, T1_2, T1_3, T1_4	2.5	T1_5, T2_4, T2_2, T2_1, T2_6	4.5	T1_5, T3_1, T3_2, T2_2	0	T1_17	10		5.2	T6_2	6.0	T7_1, T7_2	0	T1_17	9	T6_1
09204211	5	T1_1, T1_2, T1_3, T1_8	0	T1_17	6	T1_5, T3_7, T3_8, T3_4, T3_6	0	T1_17	10		7.8	T6_1	6.0	T7_1, T7_2	0	T1_17	9.5	T6_1
11216323	6	T1_1, T1_8, T1_16	6.5	T1_8, T2_4	7.5	T3_4, T3_9, T2_4	0	T1_17	10		9.6	T6_2	0	T1_17	0	T1_17	10
11216326	2.5	T1_14, T1_8, T1_7, T1_15, T1_5	0	T1_17	10		6	T4_1, T4_2	10		6.5	T6_1	7.0	T7_1, T7_3	0	T1_17	10
08000946	0	T1_17	6	T2_1, T2_2	0	T1_17	0	T1_17	0	T5_1	0	T1_17	0	T1_17	0	T1_17	10
12345678	1	T1_1,  T2_2, T1_18, T1_16, T2_4	0.5	T1_14, T2_7, T1_8, T1_16, T2_4	0	T1_17	0	T1_17	10		0.9	T6_2	0	T1_17	0	T1_17	0	T1_17
a11216316	2.8	T1_19,T1_8, T2_4	4	T1_8, T2_4	4.9	T3_11, T3_4, T3_12, T2_4	0	T1_17	0	T5_1	0	T1_17	6	T7_5, T7_6, T7_7	5.8	T6_2	10

Comentarios:

• T1_1: El ejercicio 1 contiene doble apuntador

            typedef tipoNodo *pNodo;
            typedef tipoNodo *Pila;
            Entonces cuando declaras: Pila *algo
            tu variable algo es en realidad un doble apuntador

• T1_2:   El programa del ejercicio 2a no funciona
• T1_3:   Falta ejercicio 2b
• T1_4:   Ejercicio 3 incompleto
• T1_5:   Reporte incompleto
• T1_6:   Error al liberar memoria (liberaMemoria())
• T1_7:   No convierte bien las expresiones
• T1_8:   Faltó programar el ejercicio 3
• T1_9:   Problema al retornar un char* en el ejercicio 2
• T1_10: Tu programa del ejercicio 2a no imprime los operandos, solo los operadores
• T1_11: Problema en los indices de un arreglo (en C los indices comienzan en cero)
  

            Después de calcular el tamaño de la cadena (tam), debiste empezar tu ciclo for en i=tam-1 (ejercicio 2b)

• T1_12: Para el ejercicio 2b, cuando te encuentras un ")", solo metes a la pila (no hay que sacar nada de la pila)
• T1_13: Ejercicio 3 incompleto y mal paso de parámetros:

            push(pila1,&tope1,&numero1);
            void push (int pila[],int *tope, int x)

• T1_14: Faltó programar el ejercicio 1
• T1_15: Copy + Paste de Internet (Hay que entender lo que estamos investigando)
• T1_16: Falta el reporte
• T1_17: No entregó tarea
• T1_18: En el ejercicio 3, la idea era utilizar pilas para la suma de los dos números grandes (en el slide 14 de la sesión Pilas, puedes encontrar el algoritmo)
• T1_19: En el ejercicio 2a, tu programa tiene un detalle en las comparaciones:
  

            while(precedencia(inf[i], pila[ptr]) < 0 && pila[ptr]!='(' && ptr>0)
            Hay que cuidar el orden de las comparaciones, en este caso puede quedar de la siguiente manera:
            while(ptr>0 && pila[ptr]!='(' && precedencia(inf[i], pila[ptr]) < 0)

• T2_1: En el ejercicio 3, faltó liberar la memoria y retornar el valor de "x_aux" en tu función desencolar
• T2_2: Faltó programar el ejercicio 2
• T2_3: En el ejercicio 1, no implementaste una cola circular (solo es una cola usando memoria dinámica)
• T2_4: Retardo en la entrega de la tarea
• T2_5: En el ejercicio 1, faltó programar la función desencolar (o una función donde puedas eliminar un elemento de la cola)
• T2_6: Plagio de tarea
• T2_7: Tu programa no compila, tienes problemas en el paso de parámetros: (En tu función: encolar(&primero,&ultimo,10); no puedes pasar un doble apuntador ya que en tu definición, tu función solo acepta un apuntador simple...)
  

• T3_1: Para el inciso d) del ejercicio 1, no debes perder el apuntador a la lista, es decir solo despliegas los datos, pero estos deben seguir en la lista y tu programa debería volver a desplegarlos si fuera necesario
• T3_2: Para el inciso e) del ejercicio 1, tu programa debería eliminar (usando free) solo los elementos que tengan el campo dato mayor a cierto valor
• T3_3: Para el ejercicio 2, en tu comentario: "si contiene impar, el ultimo exponente es un cero", no puedes meter el polinomio sin el cero, ya que causa un problema de desbordamiento de tu variable "polinomio"
• T3_4: Faltó implementar el inciso e) del ejercicio 1
• T3_5: El inciso c) del ejercicio 2 está incompleto
• T3_6: Faltó implementar el inciso d) del ejercicio 2
• T3_7: La condición dentro del while de tu función contador, no se puede evaluar por que no inicializaste tu apuntador "nodo_nuevo" y como la lista no es circular, debes modificar la condición
• T3_8: Faltó implementar el inciso d) del ejercicio 1
• T3_9: Faltó implementar el inciso c) del ejercicio 2
• T3_10: En el inciso e) del ejercicio 1, tu función eliminar no funciona bien ya que implementaste una lista circular y entonces cuando llegas a la siguinete sentencia:

            while(aux_bor!=NULL && (aux_bor->valor)<y)
            Tu variable aux_bor nunca va a apuntar a NULL, por lo tanto, si no tienes ningún valor en la lista que sea mayor o igual que "y" entonces tu programa entrará en un ciclo infinito…

• T3_11: En el ejercicio 1, tu función insertarInicio si funciona bien, sin embargo tu función insertar no funciona por lo siguiente:
  

            Nodo *nuevo, *aux;
            nuevo = (Nodo *) malloc(sizeof(Nodo));
            nuevo->sig=aux->sig;   //No puedes asignar a nuevo->sig una dirección que no has reservado o inicializado (aux->sig no existe)

• T3_12: En el ejercicio 2, tienes el mismo problema que en el ejercicio 1:

            Nodo *temp=inicio;
            Nodo *aux, *nuevo;
            int c, e;
            while(temp!=NULL){
                c=temp->coe;
                e=temp->exp;
                aux->coe=c*e;  //aquí aux no ha sido inicializado o asignado a una localidad de memoria, entonces no es posible asignarle algo en coe
                Nota: en tu función insertarInicio, primero reservas memoria con malloc y luego asignas los valores coe y exp (aquí sería algo similar)

• T4_1: En el inciso d) la idea era ordenar las listas, es decir realizar movimientos en los apuntadores de cada uno de los nodos para que estos estuvieran ordenados (Esto se explicó en clase). Incluso hay un avance en lista_enlazada_ordenada.cpp que pueden utilizar
• T4_2: A consecuencia de que d) no está bien, entonces e) tampoco
• T4_3: Error en la comparación: if('h' > 'jmas1')

• T5_1: No presentó

• T6_1: Comentarios enviados por correo electrónico
• T6_2: Comentarios en su reporte escrito a mano
  

• T7_1: Faltó programar el sondeo lineal 
• T7_2: Cuando se elimina un elemento de la tabla hash, el cual tiene colisiones  (la lista tiene elementos), si el elemento a eliminar está en la tabla y no en la lista, tu programa repite un elemento de la lista, faltó eliminarlo...
  

            Ejemplo: Suponga que se han dado de alta estos elementos
            Tabla Hash:
            <HELF70> <DANIEL> <1500.00> <PINOS>
            <--> <--> <--> <-->
            <HELF40> <FRANCISCO> <1000.00> <AMERICAS>--><HELF90> <PATY> <5000.00> <OAXACA>--><HELF04> <HIGINIO> <2000.00> <CHUBURNA>
            <HELF50> <NAYELI> <4000.00> <AME>
            <--> <--> <--> <-->

             Al eliminar el elemento con IFE=HELF40, pasa lo siguiente:
            Tabla Hash:
            <HELF70> <DANIEL> <5000.00> <PINOS>
            <--> <--> <--> <-->
            <HELF90> <PATY> <5000.00> <OAXACA>--><HELF90> <PATY> <5000.00> <OAXACA>--><HELF04> <HIGINIO> <2000.00> <CHUBURNA>
            <HELF50> <NAYELI> <4000.00> <AME>
            <--> <--> <--> <-->           

            Ahora, el elemento con IFE=HELF90, se repite tanto en la tabla como en su respectiva lista

            En tu programa solo basta con eliminar el nodo de la lista después de haber copiado la información, es decir, poner lo siguiente:
            elimina_en_lista(&Tabla[posicion].lista, Tabla[posicion].lista->IFE);

• T7_3: En tu función eliminar, te faltó inicializar p=0, si no hay problemas…
• T7_4: Tus programas no compilan:
• Ejercicio 1A
• a) Incorrecto: nodo_nuevo->nombre = nombre_k; --> utiliza strcpy (visto en clase...)
• b) Mal paso de parametros: desplegar(tipoNodo lista);
• Ejercico 1B
• a) Como no está definida la estructura tipoNodo, al llegar a tipoNodo *lista = NULL;, el compilador dice que no está definida
• b) La sintaxis no es buena: Tabla[indice_k] = Tabla[(indice_k)+1]):
• c) Falta un parametro o le pusiste una coma de más: void Baja(tipoTablaHash *Tabla, char *clave_k, )
• d) En tu función baja, indice_k no está definido: Tabla[indice_k] = Tabla[(indice_k)+1]):
• ...
  

• T7_5: En tu función Alta te faltó: lista->saldo = saldo_k;
• T7_6: En el encadenamiento separado no estas considerando tener una lista para cada elemento de tu tabla hash. Lo que estas haciendo es tener una lista global apuntada por "inicio". Entonces todos los elementos de la tabla hash ven la misma lista, lo cual es un error
• T7_7: En el sondeo lineal, después de la función hash, no puedes ingresar los datos directamente en el indice_k calculado, debes primero ver si hay colisión, si lo hay, entonces buscas un espacio vacío en las siguientes posiciones de la tabla y ahí es donde tienes que meter la nueva información. Lo que hace tu programa es sobreescribir la nueva información en el primer indice_k calculado (error)

Proyectos:

• Cómputo cuántico, Daniel Concha Pérez
  
• Resolución de rompecabezas, Carlos Chin Dzul
• La aplicación de grafos en la planeación de estructuras (carreteras, líneas telefónicas, circuitos eléctricos de las casas, etc), Juan Manuel Sol Cabañas
• Encriptación, Anakaren Ruiz Tamayo
• Salto del Caballo, Javier Jeremías Gurubel Romero
• Árbol biselado o Árbol Splay, Cristian Arturo Domínguez González 
• Grafos en la informática, Higinio Guadalupe Pool Tzuc
• Árboles KD, Donny de Jesus Sosa May
• Aplicación de Pilas (PostScript), Dennis Elias Hernandez Matu
  

Presentación: Jueves 27/Noviembre

Bibliografía:

• Introduction to Algorithms, Cormen, T.H., Leiserson, Ch. E., Rivest R. L., Stein, C., MIT Press, 2001.
• Data Structures and Algorithms in C++, Broks Cole, 2000.
• The Art of Computer Programming, Knuth, Donal. Addison Wesley, 1998.
• UNIX, Programer’s Reference, Valley John, J., QUE Ed., 1991.
• Estructura de datos, Cairó - Guardati, 2a. Edición, 2002.
• Programación en C : metodología, algoritmos y estructura de datos, Luis Joyanes Aguilar, Ignacio Zahonero Martínez, 2a ed., 2005.
• Estructuras de matemáticas discretas para la computación, Bernard Kolman, Robert C. Busby, Sharon Ross, 3a. ed., 1997.  
• Data structures & algorithms in JAVA, Robert Lafore, 2a ed., 2003.
  
• http://www.c.conclase.net/
• http://zomwi.blogspot.mx/2012/05/convertir-un-arbol-n-ario-binario.html
• http://www.colimbo.net/113/docu.htm
• http://www.dnatube.com/courses/mitintroalgorthm (Videos de clases en el MIT, Lec 7: Hashing I y Lec 8: Hashing II) 
• http://www.dnatube.com/courses/mitintroalgorthm (Videos de clases en el MIT, Lec 13: Breadth_First Search (BFS) y Lec 14: Depth_First Search (DFS))
• http://www.jaapsch.net/puzzles/rubslide.htm (rubik-slice game)