Seminar (Combinatorial) Algorithms, Spring 2015

Next year: Thursday February 4, 2016 - May 12, 2016 (not on May 5, 2016); 9:15-11:00.

previous years

This year: Thursdays, February 5, 2015 — May 7, 2015; 9:15-11:00; Room 403, Snellius.
Subject: "Fun with algorithms". Literature: Fun with Algorithms.

Contents | Schedule | Participants | Deliverables | References

The Seminar (Combinatorial) Algorithms is intended for Master students in Computer Science. Lectures are in English.
The seminar is organised by dr. H.J. (Hendrik Jan) Hoogeboom and dr. W.A. (Walter) Kosters.

Dates: Thursday mornings, 9:15-11:00 hours; February 5, 2015 — May 7, 2015. Room 403, Snellius.

This year's subject is "Fun with algorithms", see here.
In the first half of the semester every student presents a part from the book/papers mentioned above/below. After that students should study recent literature (or later chapters of the book) and present their results. And maybe do some programming ...
Meetings are on a weekly basis. Students can also suggest neighbouring subjects. For a somewhat more detailed list, see below.
Credit points: 6 ECTS. There is no written exam.

Prerequisites: Algorithms, Complexity, Datastructures (all at bachelor's level, see for instance the Dutch course pages Datastructures and Complexity).

Students should register in advance, in December 2014, by personal visit to the organizers. The number of participants is at most 10 (approximately :).

Contents

In this seminar we will discuss several issues dealing with algorithms, as described in the "FUN" papers mentioned above.

Students are supposed to present and discuss papers, during class. The setup depends on the number of participants.
Every student presents two papers, one in each half of the semester. Each presentation takes about 45 minutes, so in a session we have two presentations. Next to the oral presentations (using PDF or PowerPoint slides, with the additional help of the blackboard) ± ten page self-contained essays on the subject must be written (in LaTeX; in English). See here for a template. Deadline: one month after the presentation.
Essays should be improved until students and organizers agree on the contents. Students must be present during all sessions, and are supposed to actively take part in the presentations, e.g., ask questions. Immediately after each lecture there is a short discussion between students and organizers, where the presentation is evaluated. The first and second meetings are used to make a proper schedule. Every student is supposed to choose and present two subjects, one in the first half and one in the second half of the seminar.
Students should use their own laptop for the presentations. It is wise to also have the slides for the presentation on a memory-stick. A beamer is always available.

Grading The final grade is composed of the four Ps: presentation (2x), paper (2x), participation (including presence) and peer review OR programming.

Schedule

Participants

Email at Umail (or at Gmail, or ...):
nameemailremarks
Leon Helwerda l.s.helwerda (U)
Erik Hollander gerbebras (G)
Tobias Kappé tobias.kappe (G)
Anna Latour anna.latour (G)
Tim van der Meij timvandermeij (G)
Bas Nieuwenhuizen b.m.nieuwenhuizen (U)
Bart van Strien bart.bes (G)
Wilco Verhoef wilco (verhoef dot nu)
Lieuwe Vinkhuijzen l.vinkhuijzen (G)
Boyd Witte badboyd22 (G)
Niek Zuure n.b.zuure (U)

Deliverables

subject                                                who        remarks                        
Perfect matchings            Bas     [EN] first version handed in (5.3) and checked by W (11.3); second version handed in (1.5) and checked by HJ (11.5)
Nintendo games Leon [EN] ✓ first version handed in (12.3) and checked by W (13.3); second version handed in (18.3) and checked by HJ (28.4); final version handed in (29.4)
Card-based security Tobias [EN] ✓ first version handed in (12.3) and checked by W (16.3); second version handed in (19.3) and checked by HJ (30.4); final version handed in (13.5)
PIN cracking Tim [EN] ✓ first version handed in (30.3) and checked by W (1.4); second version handed in (6.4) and checked by HJ (28.4); final version handed in (29.4)
Might and Magic Boyd [EN] ✓ first version handed in (1.4) and checked by W (6.4); second version handed in (12.4) and checked by HJ (11.5); final version handed in (12.5)
Tron Bart [EN] ✓ first version handed in (11.5) and checked by W (18.5); second version handed in (27.5) and checked by HJ (31.5); final version handed in (23.6)
Kal-Toh Anna [NL] ✓ first version handed in (14.7) and checked by W (15.7); second version handed in (15.15) and checked by HJ (12.17); final version handed in
River crossing Niek [EN] ✓ first version handed in (6.8) and checked by W (11.8); second version handed in (8.9) and checked by HJ (23.9); final version handed in (25.9)
======================= ===== =====
Unfriendly subway system Leon [NL] ✓ first version handed in (5.5) and checked by W (11.5); second version handed in (19.5) and checked by HJ (16.6); final version handed in (19.6)
Divorcing made easy Boyd [NL] ✓ first version handed in (6.5) and checked by W (10.5); second version handed in (11.5) and checked by HJ (31.5); final version handed in (4.6)
Rationalized Crossword Puzzle Tim [NL] ✓ first version handed in (25.5) and checked by W (27.5); second version handed in (28.5) and checked by HJ (8.6); final version handed in (9.6)
Picture-Hanging Puzzles Tobias [NL] ✓ first version handed in (10.6) and checked by W (12.6); second version handed in (15.6) and checked by HJ (17.6); final version handed in (22.6)
Cryptographic and Physical .. Bart [NL] ✓ first version handed in (23.6) and checked by W (24.6); second version handed in (13.7) and checked by HJ (28.7); final version handed in (8.8)
Kissing problem Niek [NL] ✓ first version handed in (5.7) and checked by W (6.7); second version handed in (7.7) and checked by HJ (27.7); final version handed in (30.7)
Playing Dominoes Anna [EN] ✓ firstfirst version handed in (12.8) and checked by W (18.8); second version handed in (15.15) and checked by HJ (12.17); final version handed in
======================= ===== =====

References

Further references are either books or papers, see below. Books are usually available in room 159/162. Remember that most doi's can only be used from computers within the university domain. Many other books and the internet may be helpful.

  1. Fun with Algorithms
  2. Greg Aloupis etal. Classic Nintendo Games Are (Computationally) Hard
    (FUN 2014 doi:10.1007/978-3-319-07890-8_4)
    Note: accepted manuscript TCS doi:10.1016/j.tcs.2015.02.037
  3. Terry Anderson, Therese C. Biedl. The Vulcan Game of Kal-Toh: Finding or Making Triconnected Planar Subgraphs
    (FUN 2012 doi:10.1007/978-3-642-30347-0_4)
  4. Michael A. Bender etal. The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye
    (FUN 2012 doi:10.1007/978-3-642-30347-0_6)
    Note: final paper in ToCS doi:10.1007/s00224-013-9484-x
  5. Peter Boothe. Using Cell Phone Keyboards Is (NP) Hard
    (FUN 2010 doi:10.1007/978-3-642-13122-6_8)
  6. Michael Brand. No Easy Puzzles: A Hardness Result for Jigsaw Puzzles
    (FUN 2014 doi:10.1007/978-3-319-07890-8_6)
    Note: in press TCS doi:10.1016/j.tcs.2015.02.030
  7. Péter Burcsi etal. Normal, Abby Normal, Prefix Normal
    (FUN 2014 doi:10.1007/978-3-319-07890-8_7)
  8. Domenico Cantone, Simone Faro, Emanuele Giaquinta. Bit-(Parallelism)2: Getting to the Next Level of Parallelism
    (FUN 2010 doi:10.1007/978-3-642-13122-6_18)
  9. Yu-Feng Chien, Wing-Kai Hon. Cryptographic and Physical Zero-Knowledge Proof: From Sudoku to Nonogram
    (FUN 2010 doi:10.1007/978-3-642-13122-6_12)
  10. Erik D. Demaine etal. Picture-Hanging Puzzles
    (FUN 2012 doi:10.1007/978-3-642-30347-0_11)
  11. Erik D. Demaine, Fermi Ma, Erik Waingarten. Playing Dominoes Is Hard, Except by Yourself
    (FUN 2014 doi:10.1007/978-3-319-07890-8_12)
  12. Dimitrios I. Diochnos. Leveling-Up in Heroes of Might and Magic III
    (FUN 2010 doi:10.1007/978-3-642-13122-6_16)
  13. Jannik Dreier, Hugo Jonker, Pascal Lafourcade. Secure Auctions without Cryptography
    (FUN 2014 doi:10.1007/978-3-319-07890-8_14)
  14. Jakob Engel, Markus Holzer, Oliver Ruepp, Frank Sehnke. On Computer Integrated Rationalized Crossword Puzzle Manufacturing
    (FUN 2012 doi:10.1007/978-3-642-30347-0_15)
  15. Harrah Essed, Wei Therese. [= Joe Sawada, Aaron Williams]. The Harassed Waitress Problem
    (FUN 2014 doi:10.1007/978-3-319-07890-8_28)
  16. Rudolf Fleischer, Tao Zhang. Competitive Analysis of the Windfall Game
    (FUN 2014 doi:10.1007/978-3-319-07890-8_16)
  17. Paola Flocchini etal. Mapping an Unfriendly Subway System
    (FUN 2010 doi:10.1007/978-3-642-13122-6_20)
    Note: final paper in ToCS doi:10.1007/s00224-011-9341-8
  18. Riccardo Focardi, Flaminia L. Luccio. Cracking Bank PINs by Playing Mastermind.
    (FUN 2010 doi:10.1007/978-3-642-13122-6_21) Note: final paper in ToCS doi:10.1007/s00224-011-9340-9
  19. Martin Fürer. Counting Perfect Matchings in Graphs of Degree 3
    (FUN 2012 doi:10.1007/978-3-642-30347-0_20)
  20. Ellen Gethner etal. M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns
    (FUN 2012 doi:10.1007/978-3-642-30347-0_21)
    Note: final paper in ToCS doi:10.1007/s00224-013-9485-9
  21. Hiro Ito, Stefan Langerman, Yuichi Yoshida. Algorithms and Complexity of Generalized River Crossing Problems
    (FUN 2012 doi:10.1007/978-3-642-30347-0_24)
    Note: final paper in ToCS doi:10.1007/s00224-014-9562-8
  22. Minghui Jiang, Pedro J. Tejada, Haitao Wang. Quell
    (FUN 2014 doi:10.1007/978-3-319-07890-8_21)
  23. Mohammad Mahdian. Fighting Censorship with Algorithms
    (FUN 2010 doi:10.1007/978-3-642-13122-6_29)
  24. Tillmann Miltzow. Tron, a Combinatorial Game on Abstract Graphs
    (FUN 2012 doi:10.1007/978-3-642-30347-0_29)
  25. Takaaki Mizuki, Hiroki Shizuya. Practical Card-based Cryptography
    (FUN 2014 doi:10.1007/978-3-319-07890-8_27)
  26. Kirk Pruhs, Gerhard J. Woeginger. Divorcing Made Easy
    (FUN 2012 doi:10.1007/978-3-642-30347-0_30)
  27. Giovanni Viglietta. Lemmings Is PSPACE-Complete
    (FUN 2014 doi:10.1007/978-3-319-07890-8_29)
    Note: accepted manuscript TCS doi:10.1016/j.tcs.2015.01.055

May 12, 2016 — http://www.liacs.leidenuniv.nl/~kosterswa/semalg/index.html