392268 | Pedro Feijão | Summer 2015 | Wed 14-16, U10-146 | ekvv |
Based on original research papers, the participants will give oral presentations (20-45 min) and write short summaries (ca. 5 pages), both in English, about (not necessarily serious) algorithmic problems and their solutions.
Date | Topic | Name | Article |
08.04.2015 | Preliminaries | Pedro Feijão | — |
15.04.2015 | — | — | — |
22.04.2015 | — | — | — |
29.04.2015 | Schedule Talk Dates | Pedro Feijão | — |
06.05.2015 | — | — | — |
13.05.2015 | Talk | Pedro | TBA |
20.05.2015 | Talk | Willy / Bianca | When Zombies Attack / Die Another Day |
27.05.2015 | Talk | Hatem / Yannik | Crossing the Bridge at Night / Leveling-up in heroes of might and magic III |
03.06.2015 | Talk | Anne / Mehmood | Knitting for Fun / Zig-Zag Numberlink is NP-Complete |
10.06.2015 | Talk | Ruben / Yannik | The Urinal Problem / The Game of Life |
17.07.2015 | Hand-in Summary Report | — | — |
Andersson, D. (2007b). HIROIMONO is NP-complete. Computer, (January), 30–39.
Asano, T., Demaine, E. D., Demaine, M. L., & Uehara, R. (2010). Kaboozle is NP-complete, even in a strip. Lecture Notes in Computer Science (including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6099 LNCS, 28–36. doi:10.1007/978-3-642-13122-6_5
Baccherini, D., & Merlini, D. (2008). Combinatorial analysis of Tetris-like games. Discrete Mathematics, 308(18), 4165–4176. doi:10.1016/j.disc.2007.08.009
Bernasconi, A., Bodei, C., & Pagli, L. (2007). Knitting for Fun : A Recursive Sweater, 53–65.
Bialasiewicz, a, Brehler, R., Draeger, J., & Schmitz, H. (2008). When Zombies Attack!: Mathematical modelling of an outbreak of zombie infection, 355–365.
Böcker, S., & Lipták, Z. (2007). A fast and simple algorithm for the money changing problem. Algorithmica (New York), 48(4), 413–432. doi:10.1007/s00453-007-0162-8
Bodlaender, H. L., Tel, G., & Alt, H. (2007). Wooden Geometric Puzzles : Design and Hardness Proofs Wooden Geometric Puzzles : Design and Hardness Proofs.
Cardinal, J., Kremer, S., & Langerman, S. (2006). Juggling with pattern matching. Theory of Computing Systems, 39(3), 425–437. doi:10.1007/s00224-005-1239-x
Choice, I., & Protocol, U. (2009). Urinal protocol vulnerability, 11–13.
Demaine, E. D., Demaine, M. L., & Eppstein, D. (2000). Phutball Endgames are Hard, 42, 9. Retrieved from http://arxiv.org/abs/cs/0008025
Demaine, E. D., Hohenberger, S., & Liben-Nowell, D. (2002). Tetris is Hard, Even to Approximate, 56. doi:10.1142/S0218195904001354
Demaine, E., Demaine, M., Uehara, R., Uno, T., & Uno, Y. (2010). UNO Is Hard, Even for a Single Player. In P. Boldi & L. Gargano (Eds.), Fun with Algorithms SE - 15 (Vol. 6099, pp. 133–144). Springer Berlin Heidelberg. doi:10.1007/978-3-642-13122-6_15
Di Battista, G., Frati, F., & Patrignani, M. (2009). On embedding a graph in the grid with the maximum number of bends and other bad features. Theory of Computing Systems, 44(2), 143–159. doi:10.1007/s00224-008-9115-0
Diochnos, D. I. (2010). Leveling-up in heroes of might and magic III. Lecture Notes in Computer Science (including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6099 LNCS, 145–155. doi:10.1007/978-3-642-13122-6_16
Fleischer, R. (2008). Die Another Day. Theory of Computing Systems, 44(2), 205–214. doi:10.1007/s00224-008-9109-y
Fleischer, R., & Woeginger, G. J. (2012). An algorithmic analysis of the Honey-Bee game. Theoretical Computer Science, 452, 75–87. doi:10.1016/j.tcs.2012.05.032
Forišek, M. (2010). Computational complexity of two-dimensional platform games. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 6099 LNCS, pp. 214–227). doi:10.1007/978-3-642-13122-6_22
Ghosh, A., & Mahdian, M. (2012). Christmas Gift Exchange Games. Theory of Computing Systems, 50(1), 3–19. doi:10.1007/s00224-011-9342-7
Gradwohl, R., Naor, M., Pinkas, B., & Rothblum, G. N. (2009). Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles. Theory of Computing Systems, 44(2), 245–268. doi:10.1007/s00224-008-9119-9
Iwama, K., Miyano, E., & Ono, H. (2009). Drawing borders efficiently. Theory of Computing Systems, 44(2), 230–244. doi:10.1007/s00224-008-9117-y
Kaye, R. (2007). Some Minesweeper Configurations, 1–9.
Leigh, R., Schonfeld, J., & Louis, S. J. (2008). Using coevolution to understand and validate game balance in continuous games. Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation - GECCO ’08, 1563. doi:10.1145/1389095.1389394
Morin, P., & Morrison, J. (2004). The geometry of carpentry and joinery. In Discrete Applied Mathematics (Vol. 144, pp. 374–380). doi:10.1016/j.dam.2003.11.013
Prencipe, G., & Informatica, D. (n.d.). ON THE EFFICIENT CAPTURE OF DANGEROUS CRIMINALS, 1–13.
Rote, G. (2002). Crossing the Bridge at Night. Bulletin of the European Association for Theoretical Computer Science, 78, 241–246.
Vliet, R. Van, Hoogeboom, H. J., Deutz, A., van Vliet, R., & Hoogeboom, H. J. (2007). High Spies (or How to Win a Programming Contest). In P. Crescenzi, G. Prencipe, & G. Pucci (Eds.), Fun with Algorithms SE - 10 (Vol. 4475, pp. 93–107). Springer Berlin Heidelberg. doi:10.1007/978-3-540-72914-3_10