Refine
Year of publication
- 2015 (2) (remove)
Document Type
- Bachelor Thesis (2) (remove)
Language
- English (2)
Has Fulltext
- yes (2)
Faculty / Organisational entity
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.
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.