Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010, Proceedings

ISBN-13: 9783642131219 / Angielski / Miękka / 2010 / 382 str.

Paolo Boldi;Luisa Gargano

Opis

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

Spis treści

Fun with Olympiad in Algorithmics.- The FUNnest Talks That belong to FUN (Abstract).- Fun with Games.- Do We Need a Stack to Erase a Component in a Binary Image?.- Kaboozle Is NP-complete, Even in a Strip.- A Hat Trick.- Fun at a Department Store: Data Mining Meets Switching Theory.- Using Cell Phone Keyboards Is ( ) Hard.- Urban Hitchhiking.- A Fun Application of Compact Data Structures to Indexing Geographic Data.- On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching.- Cryptographic and Physical Zero-Knowledge Proof: From Sudoku to Nonogram.- A Better Bouncer’s Algorithm.- Tradeoffs in Process Strategy Games with Application in the WDM Reconfiguration Problem.- UNO Is Hard, Even for a Single Player.- Leveling-Up in Heroes of Might and Magic III.- The Magic of a Number System.- Bit-(Parallelism)2: Getting to the Next Level of Parallelism.- An Algorithmic Analysis of the Honey-Bee Game.- Mapping an Unfriendly Subway System.- Cracking Bank PINs by Playing Mastermind.- Computational Complexity of Two-Dimensional Platform Games.- Christmas Gift Exchange Games.- Return of the Boss Problem: Competing Online against a Non-adaptive Adversary.- Managing Change in the Era of the iPhone.- The Computational Complexity of RaceTrack.- Simple Wriggling Is Hard Unless You Are a Fat Hippo.- The Urinal Problem.- Fighting Censorship with Algorithms.- The Complexity of Flood Filling Games.- The Computational Complexity of the Kakuro Puzzle, Revisited.- Symmetric Monotone Venn Diagrams with Seven Curves.- The Feline Josephus Problem.- Scheduling with Bully Selfish Jobs.- O(1)-Time Unsorting by Prefix-Reversals in a Boustrophedon Linked List.