Paolo Baldi

Fun with Algorithms: 5th International Conference, Fun 2010, Ischia, Italy, June 2-4, 2010, Proceedings - Lecture Notes in Computer Science / Theoretical Computer Science and General Issues Paolo Baldi

Marc Notes: Includes bibliographical references and index. Table of Contents: Fun with Olympiad in Algorithmes (Invited Talk) / Roberto Grossi, Alessio Orlandi, Giuseppe Ottaviano -- The FUNnest Talks That belong to FUN (Abstract) (Invited Talk) / Prabhakar Raghavan -- Fun with Games (Invited Talk) / Paul G. Spirakis, Ioannis Chatzigiannakis, Georgios Mylonas, Panagiota N. Panagopoulou -- Do We Need a Stack to Erase a Component in a Binary Image? / Tetsuo Asano -- Kaboozle Is NP-complete, Even in a Strip / Tetsuo Asano, Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara -- A Hat Trick / Oren Ben-Zwi, Guy Wolfovitz -- Fun at a Department Store: Data Mining Meets Switching Theory / Anna Bernasconi, Valentina Ciriani, Fabrizio Luccio, Linda Pagli -- Using Cell Phone Keyboards is (NP) Hard / Peter Boothe -- Urban Hitchhiking / Marco Bressan, Enoch Peserico -- A Fun Application of Compact Data Structures to Indexing Geographic Data / Nieves R. Brisaboa, Miguel R. Luaces, Gonzalo Navarro, Diego Seco -- On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching / PEter Burcsi, Ferdinando Cicalese, Gabriele Fici, Zsuzsanna LiptAk -- Cryptographic and Physical Zero-Knowledge Proof: From Sudoku to Nonogram / Yu-Feng Chien, Wing-Kai Hon -- A Better Bouncer's Algorithm / Ferdinando Cicalese, Travis Gagie, Anthony J. Macula, Martin Milanic, Eberhard Triesch -- Tradeoffs in Process Strategy Games with Application in the WDM Reconfiguration Problem / Nathann Cohen, David Coudert, Dorian Mazauric, NapoleAo Nepomuceno, Nicolas Nisse -- UNO Is Hard, Even for a Single Player / Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara, Takeaki Uno, Yushi Uno -- Leveling-Up in Heroes of Might and Magic III / Dimitrios I. Diochnos -- The Magic of a Number System / Amr Elmasry, Claus Jensen, Jyrki Katajainen -- Bit-(Parallelism)2: Getting to the Next Level of Parallelism / Domenico Cantone, Simone Faro, Emanuele Giaquinta -- An Algorithmic Analysis of the Honey-Bee Game / Rudolf Fleischer, Gerhard J. Woeginger -- Mapping an Unfriendly Subway System / Paola Flocchini, Matthew Kellett, Peter C. Mason, Nicola Santoro -- Cracking Bank PINs by Playing Mastermind / Riccardo Focardi, Flaminia L. Luccio -- Computational Complexity of Two-Dimensional Platform Games / Michal ForiSek -- Christmas Gift Exchange Games / Arpita Ghosh, Mohammad Mahdian -- Return of the Boss Problem: Competing Online against a Non-adaptive Adversary / MagnUs M. HalldOrsson, Hadas Shachnai -- Managing Change in the Era of the iPhone / Patrick Healy -- The Computational Complexity of RaceTrack / Markus Holzer, Pierre McKenzie -- Simple Wriggling Is Hard Unless You Are a Pat Hippo / Irina Kostitsyna, Valentin Polishchuk -- The Urinal Problem / Evangelos Kranakis, Danny Krizanc -- Fighting Censorship with Algorithms / Mohammad Mahdian -- The Complexity of Flood Filling Games / David Arthur, RaphaEl Clifford, Markus Jalsenius, Ashley Montanaro, Benjamin Sack -- The Computational Complexity of the Kakuro Puzzle, Revisited / Oliver Ruepp, Markus Holzer -- Symmetric Monotone Venn Diagrams with Seven Curves / Tao Cao, Khalegh Mamakani, Frank Ruskey -- The Feline Josephus Problem / Frank Ruskey, Aaron Williams -- Scheduling with Bully Selfish Jobs / Tami Tamir -- O(1)-Time Unsorting by Prefix-Reversals in a Boustrophedon Linked List / Aaron Williams -- Author Index. Publisher Marketing: FUN with Algorithms is a three-yearlyconference that aims at attracting works which, besides a deep and interesting algorithmic content, also present amusing and fun aspects, are written with a keen wit, and are presented in a lively way. FUN isactuallyone ofthe mainmovingwheelsbehind mostofthe bestscienti?c results, and in a sense this conference answers to the unconfessed need of having a place where we can present the most lighthearted part of our work without sacri?cing precision and rigor. The 5th International Conference on Fun with Algorithms (FUN 2010) was held at Hotel Continental Terme in Ischia (Italy), June 2-4, 2010. The island of Ischia, a worldwide famous spa, sea, and tourist resort, is the ideal venue to host an event dedicated to pleasure as well as to science. The call for papers attracted54 submissions from all overthe world. Subm- ted paperswerecharacterizedbyanextremely high quality andfeaturing a large variety of topics. After a careful and thorough reviewing process, the Program Committee selected 32 papers. The program also included three invited talks by Roberto Grossi, Prabhakar Raghavan, and Paul Spirakis. Extended versions of selected papers presented at the meeting will be published in a special issue of Theory of Computing Syste