Vorlesungen Diskrete Strukturen Effiziente Algorithmen und Datenstrukturen I Parallele Algorithmen Fortgeschrittene Netzwerk- und Graphalgorithmen Proseminar Proofs from THE BOOK Schöne Algorithmen Praktikum Algorithmen-Entwurf Lehrveranstaltungen für Doktoranden Oberseminar

Oberseminar Lehrstuhl Mayr

• How primary decomposition of monoid congruences and binomial ideals is wrong

  Raum: 00.12.019
  Zeit: Dienstag, 29.02.2013, 15:30–17:00
  Vortragender: Dr. Thomas Kahle
  
  In a polynomial ring, a binomial says that two monomials are scalar multiples of each other. Forgetting about the scalars, a binomial ideal describes an equivalence relation on the monoid of exponents. Ideally one would want to carry out algebraic computations, such as primary decomposition of binomial ideals, entirely in this combinatorial language. We will present such a calculus, enabling one to compute by looking at pictures of monoids.

• Speicherplatzeffiziente q-Gramm-Indexe

  Raum: 03.09.058
  Zeit: Donnerstag, 23.02.2012, 11:00–11:30
  Vortragender: Johannes Merkle
  
  Ein wichtiges Forschungsgebiet der Bioinformatik ist das Durchsuchen von Sequenzen, die biologische Daten repräsentieren, beispielsweise DNA. Da diese Sequenzen sehr groß sein können, ist es nötig, effiziente Verfahren bei der Arbeit mit diesen Daten zu verwenden. q-Gramm-Indexe sind Indexstrukturen mit der man effizient in großen Texten Zeichenketten suchen kann. Sie haben allerdings den Nachteil, dass sie selbst sehr viel Speicher benötigen, wenn der Text sehr groß ist. Deshalb wurden diverse Ansätze entwickelt, deren Ziel es ist, die Größe von q-Gramm-Indexen zu reduzieren, darunter der n-Gram/2L sowie der VGRAM-Index. Beide sollen im Rahmen dieser Bachelorarbeit vorgestellt und - mit Fokus auf ihren Speicherbedarf - analysiert werden. Als Vergleich wird die Implementierung des q-Gramm-Index der SeqAn-Programmbibliothek verwendet, in welcher die beiden Verfahren auch implementiert wurden.

• Inequalities for the Number of Walks in Graphs

  Raum: 03.11.018
  Zeit: Mittwoch, 21.12.2011, 13:00–14:00
  Vortragender: Jeremias Weihmann
  
  We investigate the growth of the number w_k of directed walks of length k in undirected graphs as well as related inequalities. In that regard we generalize the inequalities of Erdös/Simonovits and Dress/Gutman using an inequality of Blakley/Dixon. An eigenwert approach yields the sandwich theorem which generalizes the inequalities of Dress/Gutman, Lagarias et al. and the inequality w_{2a} w_{2(a+b+c)} >= w_{2a+c} w_{2(a+b)+c} which is implied by a matrix theorem of Marcus/Newman. We show a family of lower bounds for the largest eigenvalue of the adjacency matrix which contains Nikiforovs family of lower bounds as a special case. Using the sandwich theorem, we prove the monotonicity of this general family of lower bounds. Finally, we show that the inequality w_0 w_3 >= w_1 w_2 holds for all trees while it isn't valid for general graphs. This demonstrates that there are nontrivial special cases of generalizations of the sandwich theorem that are valid if we consider nontrivial restricted graph families.

• Implementation and comparison of suffix tree representations

  Raum: 03.11.018
  Zeit: Dienstag, 20.12.2011, 10:30–11:15
  Vortragender: Alexander Aumann
  
  Searching through large amounts of sequence data plays an important role in computer science in general and in bio informatics specifically. Thus efficient indexing techniques are required, one of them being the suffix tree. Suffix trees are very large though in relation to the input sequence and this becomes a growing problem as the gap between disk storage capacity and memory size increases. Luckily there has been intensive research on this topic in the last 20 years and the purpose of this paper is to present some of the latest ideas for disk based suffix trees as well as implementing one memory based and one of the proposed disk based algorithms within the SeqAn library which is free to use for everybody who in need for sequence analysis tools. These implementations are finally evaluated, with a strong focus on the implementation of the disk based algorithm, the STTD64 proposed by Halachev, to show that they are of practical usage.

• Distributed Verification and Hardness of Distributed Approximation

  Raum: 03.11.018
  Zeit: Mittwoch, 16.11.2011, 14:00–15:15
  Vortragender: Stephan Holzer (ETH Zürich)
  
  We study the verification problem in distributed networks and show that in a distributed setting e.g. verifying that a subgraph H of a graph G is a minimum spanning tree takes much more time then actually computing a minimum spanning tree of G. We introduce a framework for a systematic study of distributed verification, and give almost tight lower bounds on the running time of distributed verification algorithms for many fundamental problems such as connectivity, spanning connected subgraph, and s - t cut verification.
  We then show applications of these results in deriving strong unconditional time lower bounds on the hardness of distributed approximation for many classical optimization problems including minimum spanning tree, shortest paths, and minimum cut. Many of these results are the first non-trivial lower bounds for both exact and approximate distributed computation and they resolve previous open questions. Our result implies that there can be no distributed approximation algorithm for minimum spanning tree that is significantly faster than the current exact algorithm, for any approximation factor.