| Nombre y Apellidos | Correo | GitHub |
|---|---|---|
| Ariel Plasencia Díaz | arielplasencia00@gmail.com | @ArielXL |
El objetivo de este trabajo es explicar y desarrollar la técnica meet in the middle, así como mostrar diversos ejercicios resueltos para una mejor comprensión del algoritmo. Dicha técnica fue introducida en 1974 por E. Horowitz y S. Sahni. Meet in the middle es una algoritmo de búsqueda que se usa cuando la entrada es pequeña, pero no tan pequeña, de tal forma que la fuerza bruta no pueda usarse. Se procede como divide y vencerás, se divide el problema en dos subproblemas, se resuelven individualmente y se combinan para arribar a una solución. Lo explicado anteriormente no siempre se puede aplicar porque los subproblemas no tienen la misma estructura que el problema original. Para un análisis más detallado puede consultar nuestro documento adjunto Meet in the Middle.
En la carpeta problems proponemos varios problemas a resolver con esta técnica. Cabe mencionar que son problemas escogidos de sitios de programación con gran prestigio.
Los códigos propuestos para los problemas anteriormente mencionados podemos encontrarlos aquí y fueron implementados en c++ como lenguaje de programación. Dicho lenguaje de programación es reconocido mundialmente en las competencias de programación competitiva ACM-ICPC por su gran eficiencia en tiempo de ejecución.
| Problemas | Sitio de Programación | Código | Resultado |
|---|---|---|---|
| Subset Sums | Sphere Online Judge (SPOJ) | subsums | ✔️ |
| Maximum Subsequence | CodeForces | maximum subsequence | ✔️ |
| Shortest Path | GeeksforGeeks | shortest path | ✔️ |
| Discrete Logarithm | GeeksforGeeks | discrete logarithm | ✔️ |
| ABCDEF | Sphere Online Judge (SPOJ) | abcdef | ✔️ |
| SUMFOUR | Sphere Online Judge (SPOJ) | sumfour | ✔️ |
Este trabajo se encuentra bajo los requerimientos de la licencia LICENSE, la cual puede consultar para más información y detalles.