1. Demostrar que el siguiente problema es NP completo: Tenemos N materias y M ayudantes. Cada ayudante es apto para dar solo un subconjunto determinado de las N materias. Se pueden asignar k < M ayudantes para dar las N materias? Pista: reducir a cobertura de vertices

2. Definición de "casi-árbol": grafo conexo de N vértices con, a lo sumo, N+8 aristas. Dar un algoritmo lineal que dado un casi-árbol devuelva un árbol de tendido mínimo

3. Resolver por division y conquista: hay N jugadores de un deporte, que juegan todos contra todos, los resultados son guardados en una matriz (M[i][j] = 1 significa que i le ganó a j). Dar un algoritmo que devuelva un array tal que el primer elemento le gane al segundo, el segundo al tercero, etc. Si M[2][1] = M[1][3] = 1, y los demás 0, sería [2, 1, 3].

4. Resolver por programación dinámica: tenemos un grafo dirigido con V_i nodos, i de 1 a n. Se cumple las propiedades:
  - Las aristas van solo de vértices menores a mayores, es decir v_1 -> v_2 puede ser, al revés no (1 -> 2)
  - Todos los grados son mayores a cero excepto d(V_n) = 0
Dar un algoritmo que de la longitud del camino más largo de v_1 a v_n en el grafo

5. Resolver con un algoritmo greedy: Tenemos n ayudantes con disponibilidad horaria (intervalos). Tenemos que armar un comité de ayudantes, que estén a cargo de los demás. Cada ayudante puede estar a cargo del conjunto de ayudantes que se superpongan en horarios con sí mismo. Dar un algoritmo eficiente y óptimo que determine y minimice la cantidad de ayudantes a poner en el comité.