Fun with Algorithms in English


392221 Huang, Melidis Winter 2015/2016 Thursday 10-12, U10-146 ekvv

Topics

The participants will give oral presentations (20-30 min) and write short summaries (for example 5 pages), both in English, based on research publications for algorithms which solve fun problems.

Schedule

Date Topic Name Article
22.10.2015 Preliminaries + Teaser Liren Huang, Damianos Melidis first_session2015.pdf
29.10.2015 How to read a scientific article Liren Huang, Damianos Melidis how_to_read.pdf
5.11.2015 How to write and present Liren Huang, Damianos Melidis write_present.pdf
12.11.2015 Zombie Attack Dennis Paulus canceled
19.11.2015 Uniral problem Christian Fortmann (Rehearsal) -
26.11.2015 Uniral problem Christian Fortmann (Present) TBA
26.11.2015 Cellular automata Ano Mesanovic (Rehearsal) -
26.11.2015 Die another day Tilman Lüttje (Rehearsal) -
03.12.2015 Cellular automata Ano Mesanovic (Present) TBA
03.12.2015 Die another day Tilman Lüttje (Present) TBA
03.12.2015 RSA algorithm Mert Ince (Rehearsal) -
03.12.2015 Christmas exchange problem Nhat Dinh Tien (Rehearsal) -
10.12.2015 RSA algorithm Mert Ince (Present) TBA
10.12.2015 Christmas exchange problem Nhat Dinh Tien (Present) TBA
17.12.2015 Uniral problem Christian Fortmann (Report) TBA
24.12.2015 Cellular automata Ano Mesanovic (Report) TBA
24.12.2015 Die another day Tilman Lüttje (Report) TBA
31.12.2015 RSA algorithm Mert Ince (Report) TBA
31.12.2015 Christmas exchange problem Nhat Dinh Tien (Report) TBA

Selected Papers

Credits to Pedro(!),

  • Bianca Frommer - Fleischer, R. (2008). Die Another Day. Theory of Computing Systems.
  • Willy Robin Kinne Wati - Bialasiewicz, a, Brehler, R., Draeger, J., & Schmitz, H. (2008). When Zombies Attack!: Mathematical modelling of an outbreak of zombie infection, 355–365.
  • Mehmood Ghaffar - Aaron Adcock, Erik D. Demaine, Martin L. Demaine, Michael P. O'Brien, Felix Reidl, Fernando Sánchez Villaamil, Blair D. Sullivan. (2014). Zig-Zag Numberlink is NP-Complete.
  • Anne Heidelmann - Bernasconi, A., Bodei, C., & Pagli, L. (2007). Knitting for Fun : A Recursive Sweater, 53–65.
  • Hatem Shugaa Addin - Rote, G. (2002). Crossing the Bridge at Night. Bulletin of the European Association for Theoretical Computer Science, 78, 241–246.
  • Yannik Bramkamp- 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.

References

Fun with algorithms - Conference Proceedings

Springer page for the proceedings: 2014, 2012, 2010 and 2007.

Misc. References

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

Download papers

Most of the papers on this list can be found here.

Back to Teaching