AG Algorithmen und Komplexität
>

Sommersemester 2017

Sebastian bietet im Sommersemester 2017 die Vorlesungen Advanced Algorithmics an.


 

Sebastian Wild

Email:   This email address is being protected from spambots. You need JavaScript enabled to view it.

PGP Key:   8B149255
Personal Website:   wild-inter.net
ORCID   0000-0002-6061-9177
Google Scholar   aMyZiK0AAAAJ
DBLP   publication list
Tel:   +49 631 205 2651
Fax:   +49 631 205 2573
Office:   Building 48, Room 660
Address:  

Postfach 3049
67663 Kaiserslautern

→ Publications
→ Teaching

Research Interests

My interests span several (loosely related) topics, including (but not limited to):

  • Analytic Combinatorics
    Counting fancy structures by generating function techniques.
    If you don't know generating functions, get infected: Why Generating Functions Rule
  • Practical Algorithmics
    In-detail “in vivo” analyses of real-world algorithms, both analytically and experimentally.
    See the work on Java 7's Dual-Pivot Quicksort. This article gives a brief summary of my findings.
  • (Semi-) Automatic Algorithm Analysis
    Empirically estimating asymptotic growth of expected costs of algorithms.
    Check out our tool MaLiJAn!
  • Bioinformatics
    • RNA structure prediction methods
    • Biodiversity estimation, see JAguc
  • Game Theory
    Evolutionary models, especially attempts to explain the evolution of cooperation, formation of reputation and societies.

Publications

  • Median-of-k Jumplists
    Markus E. Nebel, Elisabeth Neumann, and Sebastian Wild
    arXiv
  • Sorting Discrete i.i.d. Inputs: Quicksort is Optimal
    Sebastian Wild
    arXiv
  • Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential
    Sebastian Wild
    Doktorarbeit (Ph.D. Thesis)
    pdf, KLUEDO, ISBN, slides (defense)
  • Why is Dual-Pivot Quicksort Fast?
    Sebastian Wild
    extended abstract for Theorietage 2015 (GI Workshop on Algorithms)
    Tagungsband, arXiv, slides
  • A Simple and Fast Linear-Time Algorithm for Proportional Apportionment
    Raphael Reitzig and Sebastian Wild
    arXiv
  • Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts
    Raphael Reitzig and Sebastian Wild
    arXiv
  • Analysis of Branch Misses in Quicksort
    Conrado Martínez, Markus E. Nebel and Sebastian Wild
    Meeting on Analytic Algorithmics and Combinatorics (ANALCO15)
    SIAM, arXiv, slides, DOI: 10.1137/1.9781611973761.11
  • Analysis of Pivot Sampling in Dual-Pivot Quicksort
    Markus E. Nebel, Sebastian Wild and Conrado Martínez
    Algorithmica 75, 4, pp 632-683 (August 2016)
    springerlink, arXiv, DOI:10.1007/s00453-015-0041-7
    full version of the conference paper:
    Pivot Sampling in Dual-Pivot Quicksort
    Markus E. Nebel and Sebastian Wild
    International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms 2014 (AofA14)
    arXiv, slides, proceedings
  • Evolution of Indirect Reciprocity in Lattice Populations:
    Reputation-Based Cooperation in Prisoner's Dilemma and Snowdrift Games
    Jano Costard, Sándor P. Fekete, Hella-Franziska Hoffmann, Alexander Koch, Dominik Leipold, Jonas Radbruch, Maximilian Schlund, Jann Spiess, Paul Stursberg and Sebastian Wild
    submitted
  • Analysis of Quickselect under Yaroslavskiy's Dual-Pivoting Algorithm
    Sebastian Wild, Markus E. Nebel and Hosam Mahmoud
    Algorithmica 74, 1, pp 485-506 (
    springerlink, arXiv, DOI: 10.1007/s00453-014-9953-x
    also partially covered in Quickselect under Yaroslavskiy's Dual-Pivoting Algorithm
    Talk at the International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms 2013 (AofA13):
    slideshare, slides
  • Average Case and Distributional Analysis of Dual Pivot Quicksort
    Sebastian Wild, Markus E. Nebel and Ralph Neininger
    ACM Transactions on Algorithms 11, 3, Article 22 (January 2015)
    Author-ized pdf, arXiv, DOI: 10.1145/2629340
    full version of the conference paper:
    Average Case Analysis of Java 7’s Dual Pivot Quicksort
    Sebastian Wild and Markus E. Nebel,
    European Symposium on Algorithms 2012 (ESA12)
    in L. Epstein and P. Ferragina (Eds.): ESA 2012, LNCS 7501, Springer, 2012, 825-836.
    Best Paper Award ESA 2012
    Referenced in Sedgewick's algorithms textbook! (see Chapter 2)
    arXiv, slides, DOI: 10.1007/978-3-642-33090-2_71
    Check out the animated visualization of the algorithm (thanks to Brad Lyon)!
  • Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn
    Sebastian Wild, Markus E. Nebel, Raphael Reitzig and Ulrich Laube
    SIAM Meeting on Algorithm Engineering & Experiments 2013 (ALENEX13)
    pdf, slides, DOI: 10.1137/1.9781611972931.5
  • JAguc - a software package for environmental diversity analyses
    M. E. Nebel, S. Wild, M. Holzhauser, L. Hüttenberger, R. Reitzig, M. Sperber, T. Stoeck,
    Journal of Bioinformatics and Computational Biology (2011) 9 (6): 749-773
    pdf, DOI: 10.1142/S0219720011005781
  • Java 7's Dual Pivot Quicksort
    Master Thesis
    Available as printed paperback (AV Akademikerverlag, 2014)
    preprint pdf, ISBN: 978-3-639-67967-0!
    pdf, KLUEDO
  • An Earley-style Parser for Solving the RNA-RNA Interaction Problem
    Bachelor Thesis
    pdf, KLUEDO

Supervised Theses

  • Randomized Jumplists with Several Jump Pointers
    Elisabeth Neumann, Bachelor Thesis
    KLUEDO

Teaching

SS 17: Advanced Algorithmics, Competitive Programming

Past Teaching assistance


WS 16/17: Algorithmen und Datenstrukturen (OLAT)
WS 15/16: Algorithm Engineering and Computational Biology II
WS 14/15: Entwurf und Analyse von Algorithmen
SS 14: Algorithm Engineering and Computational Biology II
WS 13/14: Computational Biology I and Beweistechniken
SS 13: Kombinatorische Algorithmen
WS 12/13: Computational Biology II and Beweistechniken

As a student, I was tutor for the lectures Softwareentwicklung I, Softwareentwicklung III and Formale Grundlagen der Programmierung.

Fun Stuff