## Bachelor Thesis

### Refine

#### Faculty / Organisational entity

#### Document Type

- Bachelor Thesis (3) (remove)

#### Language

- English (3) (remove)

#### Keywords

- Randomized Jumplists With Several Jump Pointers (2015)
- In 2003, a dictionary data structure called jumplist has been introduced by Brönnimann, Cazals and Durand. It is based on a circularly closed (singly) linked list, but additional jump-pointers are added to provide shortcuts to parts further ahead in the list. The original jump-and-walk data structure by Brönnimann, Cazals and Durand only introduces one jump-pointer per node. In this thesis, I add one more-jump pointer to each node and present algorithms for generation, insertion and search for the resulting data structure. Furthermore, I try to evaluate the effects on the expected search costs and the complexity of the generation and insertion. It turns out that the two-jump-pointer variant of the jumplist has a slightly better prefactor (1.2 vs. 2) in the leading term of the expected internal path length than the original version and despite the more complex structure of the two-jump-pointer variant compared to the regular jumplist, the complexity of generation and insertion remains linearithmic.

- Freeness of hyperplane arrangements with multiplicities (2015)
- This bachelor thesis is concerned with arrangements of hyperplanes, that is, finite collections of hyperplanes in a finite-dimensional vector space. Such arrangements can be studied using methods from combinatorics, topology or algebraic geometry. Our focus lies on an algebraic object associated to an arrangement \(\mathcal{A}\), the module \(\mathcal{D(A)}\) of logarithmic derivations along \(\mathcal{A}\). It was introduced by K. Saito in the context of singularity theory, and intensively studied by Terao and others. If \(\mathcal{D(A)}\) admits a basis, the arrangement \(\mathcal{A}\) is called free. Ziegler generalized the concept of freeness to so-called multiarrangements, where each hyperplane carries a multiplicity. Terao conjectured that freeness of arrangements can be decided based on the combinatorics. We pursue the analogous question for multiarrangements in special cases. Firstly, we give a new proof of a result of Ziegler stating that generic multiarrangements are totally non-free, that is, non-free for any multiplicity. Our proof relies on the new concept of unbalanced multiplicities. Secondly, we consider freeness asymptotically for increasing multiplicity of a fixed hyperplane. We give an explicit bound for the multiplicity where the freeness property has stabilized.

- An Earley-style Parser for Solving the RNA-RNA Interaction Problem (Bachelor Thesis) (2010)
- It has been observed that for understanding the biological function of certain RNA molecules, one has to study joint secondary structures of interacting pairs of RNA. In this thesis, a new approach for predicting the joint structure is proposed and implemented. For this, we introduce the class of m-dimensional context-free grammars --- an extension of stochastic context-free grammars to multiple dimensions --- and present an Earley-style semiring parser for this class. Additionally, we develop and thoroughly discuss an implementation variant of Earley parsers tailored to efficiently handle dense grammars, which embraces the grammars used for structure prediction. A currently proposed partitioning scheme for joint secondary structures is transferred into a two-dimensional context-free grammar, which in turn is used as a stochastic model for RNA-RNA interaction. This model is trained on actual data and then used for predicting most likely joint structures for given RNA molecules. While this technique has been widely used for secondary structure prediction of single molecules, RNA-RNA interaction was hardly approached this way in the past. Although our parser has O(n^3 m^3) time complexity and O(n^2 m^2) space complexity for two RNA molecules of sizes n and m, it remains practically applicable for typical sizes if enough memory is available. Experiments show that our parser is much more efficient for this application than classical Earley parsers. Moreover the predictions of joint structures are comparable in quality to current energy minimization approaches.