panthema / tags / university
STXXL simple logo

Released STXXL 1.4.0

Posted on 2013-12-12 16:50 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ university stxxl

STXXL is an implementation of the C++ standard template library STL for external memory (out-of-core) computations, i.e., STXXL implements containers and algorithms that can process huge volumes of data that only fit on disks. While the compatibility to the STL supports ease of use and compatibility with existing applications, another design priority is high performance.

The project was originally created by Roman Dementiev and Peter Sanders at MPI Informatik in Saarbrücken. It moved to Karlsruhe with them in 2004. After Roman's PhD defense, there was a cooperation with the Algorithm Engineering group at the University of Frankfurt to create better parallel asynchronous sorting. Afterwards, stewardship moved to Frankfurt, where work on flash/SSD drives and various external memory graph algorithms was done.

After a longer stretch without further work, I have decided to take part in future development as a maintainer. This is partly due to my previous experience with it while implement in eSAIS, the external memory suffix and LCP array construction algorithm. And thus, today, the first release of the new 1.4 branch was published:

What's new in 1.4.0 ?


The Sound of Sorting demo program

Published "The Sound of Sorting" 0.6

Posted on 2013-05-22 23:50 by Timo Bingmann at Permlink with 2 Comments. Tags: c++ university fun sorting

This post announces the publication of my demo program for integer string sorting algorithms, called "The Sound of Sorting". It both visualizes the internals of sorting algorithms, and generates sound effects from the values being compared!

The demo is implemented using the cross-platform toolkits wxWidgets and SDL, can be executed on Windows, Linux and Mac, and runs in real time.

There are also many videos of the sorting algorithm on my new YouTube channel.

See the Sound of Sorting project page for the demo program and source code, and more information about version 0.6.

The QuadClip Algorithm

Finding Roots of Polynomials by Clipping - Report and Implementation from my Lab Course in Numerical Mathematics

Posted on 2012-03-20 22:29 by Timo Bingmann at Permlink with 0 Comments. Tags: maths university c++

This semester I had the pleasure to take part in a lab exercise course supervised by Prof. Thomas Linß at the FernUniversity of Hagen. The objective was to comprehend, implement and evaluate a particular recent advancement in the field of numerical mathematics. My topic was finding the roots of a polynomial by clipping in Bézier representation using two new methods, one devised by Michael Bartoň and Bert Jüttler [1], the other extended from the first by Ligang Liu, Lei Zhang, Binbin Lin and Guojin Wang [2].

My implementation of this topic was done for the lab course in C++ and contains many in themselves interesting sub-algorithms, which are combined into the clipping algorithms for finding roots. These sub-algorithms may prove useful for other purposes, which is the main reason for publishing this website. Among these are:

For the lab course I wrote two documents, both in German: one is an abstract Kurzfassung.pdf Kurzfassung.pdf (1 page), which is translated into English below, and the other a short report Ausarbeitung.pdf Ausarbeitung.pdf (6 pages). The report contains a short description of the algorithms together with execution and convergence speed measurements, which verify the original authors experiments. For presenting the lab work I created these Slides.pdf Slides.pdf, which however are not self-explanatory due to my minimum-text presentation style.

This blog entry continues on the next page ...

Drawing of PG(2,3)

Vervollständigung meiner Seminararbeit in Diskreter Mathematik

Posted on 2011-08-31 20:12 by Timo Bingmann at Permlink with 0 Comments. Tags: maths university

Heute habe ich meine Seminararbeit in Diskreter Mathematik an der FernUni Hagen vervollständigt. Ich möchte mich bei Prof. Hochstättler bedanken für die erfahrene Leitung und planvolle Einführung in die interessanten Gebiete der Design Theorie und endlicher Geometrien. Die Arbeit ist auf deutsch und unter folgendem Link downloadbar.

Download PDF: Seminararbeit-Singer-Differenzenmengen.pdf Seminararbeit-Singer-Differenzenmengen.pdf.

Zusammenfassung

Die Entwicklung von Differenzenmengen in der Design Theorie begann 1938 mit einer algebraischen Untersuchung endlicher projektiver Geometrien von James Singer. Nach Einführung der wichtigsten Grundbegriffe der Design Theorie und projektiver Geometrien werden in dieser Ausarbeitung die beiden Resultate von Singer entwickelt. Die Existenz einer Kollineation mit Periode \frac{n^{d+1}-1}{n-1} führt zur Definition von Differenzenmengen und beide Ergebnisse liefern elegante Konstruktionsverfahren für PG(d,p^k).


Thumbnail of three slides from completion talk

Completion Talk on My Diploma Thesis / Abschlussvortrag zu meiner Diplomarbeit

Posted on 2009-06-26 13:30 by Timo Bingmann at Permlink with 0 Comments. Tags: ns-3 talk university

Today I gave the final completion presentation for my diploma thesis. The talk showcased a selection of results published in the thesis. Results and experiments are only sketched, as all further detailed information can be found in the thesis PDF itself.

The talk contains side-by-side comparison plots of feature enhancements made to ns-3 and verifications thereof using ns-2. Furthermore, the EDCA extensions implemented in ns-3 are tested against analytically calculated reference values. In the end, a speed test comparison is done between ns-2 and ns-3, which uses the implemented classes to run an experiment scenario identically on both simulators.

The slides are available as PDFs in following two variants:

Presentation Slides (including appendix): ns-3-wifiex-completion-slides.pdf 1455 kB
Presentation Slides (two per page, excluding appendix): ns-3-wifiex-completion-slides-1x2.pdf 1040 kB

Here the table of contents:

  1. Thesis Objectives
  2. Enhancements
    1. Propagation Loss Models
    2. Reception Criteria
    3. Frame Capture Effect
    4. EDCA Implementation
  3. Speed Comparison
  4. Conclusion
  5. Appendix
    1. Enlarged Plots and Figures
      1. Propagation Loss Models
      2. Reception Criteria
      3. Frame Capture Effect
      4. EDCA Implementation

Thumbnail of front page of thesis

Finished My Diploma Thesis on 802.11 in ns-3

Posted on 2009-04-29 17:30 by Timo Bingmann at Permlink with 2 Comments. Tags: ns-3 university

After a very exhausting last week with lots of writing and little sleep, my diploma thesis is finally complete. The thesis is on enhancements to the 802.11 model and EDCA (enhanced distributed coordination access) QoS (quality of service) extensions in the new network simulator ns-3.

The thesis is written in English and a copy of the abstract and table of contents is located below. There is also a Zusammenfassung in German.

It is available as PDF in different variants:

Standard PDF version: thesis-bingmann-ns-3-wifi.pdf (3469 kB)
Better printable version (with black links): in RGB color with binding offset (3482 kB)
in CMYK color with binding offset (3381 kB)

Beyond the thesis itself, an extra page contains additional material like the source code, plot results and a snapshot of ns-3 at that time.

Shortened Table of Contents

This blog entry continues on the next page ...

Thumbnail of two slides in halftime talk

Halftime Talk on My Diploma Thesis / Zwischenvortrag zu meiner Diplomarbeit

Posted on 2009-02-06 17:30 by Timo Bingmann at Permlink with 2 Comments. Tags: ns-3 talk university

For the last three months I have been working intensely on my diploma thesis. The thesis will be about 802.11 enhancements and EDCA QoS extensions in the new network simulator ns-3.

Today I gave my halftime presentation about the current status of my efforts. The talk is composed of a short introduction into ns-3, followed by a detailed discussion of WLAN packet reception criteria and finishes with a review of DCF and how EDCA extends it.

Be warned: many slides are not all self-explanatory and therefore less suitable as a casual introduction into the topics. They are slides meant for presentation.

The slides are available as PDFs in following three variants:

Presentation Slides (including "Animations"): ns-3-wifiex-halftime-slides.pdf 1076 kB
Handout Slides (one per page): ns-3-wifiex-halftime-handout.pdf 1036 kB
Handout Slides (four per page): ns-3-wifiex-halftime-handout-2x2.pdf 1028 kB

Here the table of contents:

  1. ns-3 Basics
    1. Introduction
    2. Showcase: Design Patterns
    3. Current State
  2. Wifi in ns-3
    1. State of 802.11
    2. PHY Layer
    3. Signals, Noise and Interference
    4. Short Recapitulation of DCF
    5. QoS with EDCA
  3. Conclusion

Thumbnail of first slide of presentation

NetFundamentals Seminar - Presentation Today

Posted on 2007-01-29 19:00 by Timo Bingmann at Permlink with 0 Comments. Tags: netfundamentals university talk

Following up on the technical report, today Dimitar and myself gave a 70min presentation on Robert Gallager's Minimum Delay Routing Algorithm Using Distributed Computation. It finished my work for the NetFundamentals seminar, which was organized by Decentralized Systems and Network Services Research Group at the Institute of Telematics. The seminar was very profound and extensively dug into the mathematics of six fundamental networking papers. Besides that it was great fun and opened some new horizons.

Our presentation can be downloaded as PDF (553 KB), with two slides per page or even with four per page.

Furthermore our listeners were given an equation sheet (139 KB) to aid them in following the many formulas.


Thumbnail of a network in the NetFundamentals Technical Report

NetFundamentals Seminar - Technical Report Finished

Posted on 2006-12-19 18:19 by Timo Bingmann at Permlink with 0 Comments. Tags: netfundamentals university

Today the technical report on Robert Gallager's Minimum Delay Routing Algorithm Using Distributed Computation was finished. It is part of my work for the NetFundamentals seminar organized by Decentralized Systems and Network Services Research Group at the Institute of Telematics. In the seminar six of the computer science papers most worth reading are reviewed and presented. The technical report was written by Dimitar Yordanov and myself and a presentation will follow.

The technical report can be downloaded as PDF (470 KB)

Abstract

One of the computer science papers most worth reading is Gallager's algorithm for minimum delay routing. The merit of Gallager's paper is its rigorous mathematical approach to a problem, which is more often taken care of using heuristics. The approach is founded on a well designed mathematical network model, which is custom-tailored to describe the minimum total delay routing problem. Mathematical observations on the model lead to two conditions for achieving global optimization, which are based on the marginal delay of links and neighbors. From these observations and conditions an iterative, distributed routing algorithm is naturally derived. Gallager finishes his analysis by proving in detail that the algorithm achieves total minimum delay routing. Algorithm and model are reviewed and illustrated in detail in this technical report.

SDIOS06 Shell Screenshot

SDIOS06 - Source Code and Ready-To-Run Image

Posted on 2006-09-14 09:26 by Timo Bingmann at Permlink with 2 Comments. Tags: sdios06 university c++

As promised the source code to SDIOS06 was released under the GPL.

SDIOS06 is a toy operating system developed during the practical course SDI (System Design and Implementation) at the Systems Architecture Group of the University of Karlsruhe. It was designed and written by Timo Bingmann, Matthias Braun, Torsten Geiger and Andreas Mähler. Two games were ported to a custom SDL implementation using the VMware "hard"-ware: SDLjump and SuperTux. For more information and screenshots see my blog entry 20060727-SDI-Demo.

The source code archive was published on the L4Ka.org page: http://www.l4ka.org/86.php

A local copy of the source archive (7.4 MB) is available as well. The README file contains a great deal of information about SDIOS06's design and modules. The complete source code can be browsed on the web.

To make demonstration as easy as possible a ready-to-run binary vmware image (3.8 MB) can be downloaded. The image contains SDIOS06 installed on a virtual vmware disk image. The VMware image can be run using the free VMware Player.


Front page of slides

Talk about Study Thesis - Slides and Movie

Posted on 2006-08-02 19:43 by Timo Bingmann at Permlink with 0 Comments. Tags: compsci study thesis graphviz university talk

At the University of Karlsruhe it is common to give a concluding talk after finishing a study thesis (Studienarbeit). I presented my study thesis "Visualisation of Very Large Graphs" today at the mid-day seminar of the Theoretical Computer Science Group. The slides of the talk are available as PDFs below:

studythesis-talk-visualisation.pdf (1.6 MB) - also available with two slides per page (1.6 MB)or four slides per page (1.6 MB).

During the talk I showed a movie, in which a r-tree of the autobahnen of Germany is constructed incrementally. I actually produced two movies for this purpose: in the first the edges are added in a given sequential order and in the second the order is randomized. Both movies are encoded using transcode and the XviD codec.

Sequential Movie (3.6 MB)
Randomized Movie (5.1 MB)

The talk was received very well, and I may continue in this field with my diploma thesis.

The visualisation library is used by a route planning algorithm developed at the Theoretical Computer Science Group. By integrating my study thesis it was possible to create a Java web applet which animates the route planning algorithm. The Java applet is currently available at http://algo2.iti.uni-karlsruhe.de/schultes/hwy/demo/.

This blog entry continues on the next page ...

SVG Logo der Universität Karlsruhe

Posted on 2006-08-01 19:22 by Timo Bingmann at Permlink with 2 Comments. Tags: university

Für meinen morgigen Vortrag zur Studienarbeit, habe ich (viel zu) lange nach einem vektor-gezeichneten Logo der Univerisität Karlsruhe (TH) gesucht. Es war nur sehr schwer eines zu finden. Aus einem nach langen Stöbern gefundenen PDF habe ich dann folgende SVG, PDF und EPS Grafiken mit Inkscape erzeugt, die bestimmt jemand anderem etwas Mühe ersparen:

UniKa Logo Farbig SVG SVG (Inkscape) EPS PDF
UniKa Logo Graustufen SVG SVG (Inkscape) EPS PDF

Hinweis: Die Grafiken sind keineswegs offiziell oder sonst wie von der Univerität bereitgestellt.


Presented Practical Work for SDI (System Design and Implementation)

Posted on 2006-07-27 20:00 by Timo Bingmann at Permlink with 0 Comments. Tags: sdios06 university

Today was the final demo presentation day for the practical course SDI (System Design and Implementation) at the Systems Architecture Group of the University of Karlsruhe. Goal of the course was to implement a simple operating system on top of the L4 microkernel, which is developed at the Group.

SDIJump

Our practical course group was one of the two groups to demonstrate a working system on the last day of the semester. The presented operating system contained following basic components:

Furthermore we utilized the VMWare video "card" to enable graphics output. The "hardware" is well documented in the source code to the X11 video driver contributed by VMWare.

The frame buffer and keyboard input was linked up to a ported SDL implementation. After adding a lot of POSIX library function calls like fopen, opendir and getenv, it was possible to compile our favourite games: SDLjump and SuperTux. Both run very well on our operating system from scratch project.

Some screenshots of the shell, sdijump and supertux are available. In future the whole source code and compiled binary images may become available

A big thank you to my friends Matthias Braun, Torsten Geiger and Andreas Mähler, who made this practical work possible and especially fun!

This blog entry continues on the next page ...

Studienarbeit "Visualisierung sehr großer Graphen" fertiggestellt

Posted on 2006-06-20 17:31 by Timo Bingmann at Permlink with 0 Comments. Tags: compsci study thesis graphviz university c++

Heute habe ich meine Studienarbeit "Visualisierung sehr großer Graphen" am Institut für Theoretische Informatik fertig gestellt und abgegeben. Die Studienarbeit ist eine 3-4 monatige wissenschaftliche Arbeit und dient als Vorbereitung auf die Diplomarbeit.

Die Studienarbeit kann zum Durchlesen als PDF (2,4 MB) herunter geladen werden. Auf diesen Abschnitt folgenden die deutsche und englische Zusammenfassung der Arbeit. Weiter gibt es eine Version zum Ausdrucken (PDF 15,3 MB) mit einer hochauflösenden Vektorgraphik im Anhang.

Zusammenfassung

In dieser Studienarbeit wird untersucht, mit welchen Methoden sehr große Graphen wie ein Straßennetzwerk von Europa effizient und komfortabel visualisiert werden können. Als Ausarbeitung entsteht ein C++ Rahmenwerk für die Datenhaltung eines Graphen mit Attributen und ein Java Applet, das mit dem Datenhaltungs-Server mittels CORBA kommuniziert. Das Rahmenwerk kann leicht in bestehende Graphanwendungen integriert werden, um deren Algorithmen zu animieren.

Als Basis-Graphstruktur wird ein Adjazenz-Array verwendet und um Strukturen erweitert, die zu jedem Knoten und jeder Kante beliebig viele Attributwerte speichern. Zwei der Knotenattribute werden als Zeichenkoordinaten verwendet. Der Grundgraph und die Datenhaltung der Attributwerte wird auf möglichst kompakte Art und Weise gelöst. Graphanwendungen können eine Liste von temporären Änderungen erzeugen, die mit dem großen globalen Graphen zusammengeführt werden können. Um das Vorgehen der Graph-Algorithmen zu visualisieren, werden deren Funktionsaufrufe in einer Änderungsfolge kodiert, welche als Animation zum Java Client übertragen wird.

Um die Geschwindigkeit einer Ausschnittsanfrage zu erhöhen, wird die mehrdimensionale Indexstruktur R-Tree verwendet. Diese ermöglicht Anfragezeiten, die linear zur Anzahl der zurückgelieferten Kanten und unabhängig vom gewählten Ausschnitt sind. Es können komplexe Filterausdrücke aus Vergleichsbedingungen mit boolschen und arithmetische Operatoren verwendet werden, um die angezeigten Kanten in einem Visualisierungsauschnitt einzuschränken und so komfortabel bestimmte Aspekte der Anwendungs-Algorithmen zu untersuchen oder hervorzuheben.

Als Referenzanwendung wird das Rahmenwerk von der am Institut für Theoretische Informatik in Karlsruhe entwickelten Routenplanungsanwendung zur Visualisiserung mittels Web Applet verwendet.

Abstract

This study thesis investigates and implements methods used to efficiently visualize very large graphs like a street network of Europe. A C++ server framework is designed, which implements a data management library for graphs with attributes. A Java applet communicates with the data server via CORBA and draws sections of the graph. The graph data management library can easily be integrated into existing graph application to visual and animate calculations.

The data management library uses the adjacency array structure for representing the base graph. It is extended by similar data structures to hold an arbitrary number of attributes for each vertex and edge. The data structures are optimized towards highest storage efficiency. To modify the static global graph an application may construct a list of changes, which are efficiently merged into permanent data storage. To visualize the workings of an algorithm its function call sequence can be recorded into a list of graph changes. This change time line can be transfered to the Java client and displayed as an animation.

To accelerate access to arbitrary sections of the graph the spatial index structure R-Tree is used. It enables query times to linearly increase with the number of returned edges and be independent of the section size or position.

Furthermore complex filter expressions including comparisons and arithmetic operators can be applied to limit the displayed edges. This enables the client to explore the graph's details comfortably and highlight interesting aspects of an algorithm.

The graph data management library is used in a route planning application, which is being developed in a research group of the University of Karlsruhe. It will be used to visualize the route using a web applet.


Thumbnail of a slide from the Name Service Design talk

Talk in SDI Lab: Naming Service Design in a Multi-Server Operating System

Posted on 2006-06-01 17:00 by Timo Bingmann at Permlink with 0 Comments. Tags: sdios06 university talk

As part of my work for the SDI Lab work this summer, I held a short talk about how to design a name service in a multi-server operating system like L4.

The slides are available here:

1 Slide per page: NameServiceDesign.pdf 163 kB
2 Slides per page: NameServiceDesign-1x2.pdf 163 kB
4 Slides per page: NameServiceDesign-2x2.pdf 158 kB

Here the table of contents:

  1. Goals
  2. Name Catalogs
    1. Object Representation
    2. Catalogs
  3. IDL Interfaces
    1. Resolve Interface
    2. Bind Interface
  4. Extension / Ideas

Homepage zu meinem Tutorium zu Info3 im WS2005

Posted on 2005-11-16 20:09 by Timo Bingmann at Permlink with 0 Comments. Tags: university compsci tutorium

Hier findet man noch die alte Homepage, welche ich im WS2005 für mein Tutorium in Info3 gemacht habe.

Dort konnten meine Tutoranden ihren Punktestand und eventuelle Neuigkeiten abfragen.


Thumbnail der ersten Seite

Info2 SS2005 Probeklausur der Tutoren

Posted on 2005-07-11 19:11 by Timo Bingmann at Permlink with 0 Comments. Tags: university compsci tutorium

Zum Abschluss der Tutorien von Informatik 2 im Sommersemester 2005 haben die Tutoren zusammen eine Probeklausur erstellt. Diese wurde im letzten Tutorium geschrieben und anschließend einige Lösungshinweise zu den schwierigeren Aufgaben gegeben.

Kopie der ursprünglichen Veröffentlichung:

Achtung: Die auf dieser Seite bereitgestellten Aufgaben spiegeln die Meinung der Tutoren der Vorlesung Informatik 2 wieder. Die Aufgaben stammen nicht von den Verantwortlichen der Informatik 2 Vorlesung. Die Aufgaben sind lediglich als Hinweis zur Vorbereitung der Klausur gedacht. Die Aufgaben der Probeklausur decken nur einen Teil des gesamten Stoffes der Informatik 2 Vorlesung ab. Auch Themen, die in der Probeklausur nicht behandelt werden, sind Teil des Vorlesungstoffes und können in der offiziellen Informatik 2 Klausur behandelt werden.

Alle Tutoren werden die Probeklausur in ihrem Tutorium schreiben lassen, dies erfolgt entweder in der vorletzten oder letzten Vorlesungswoche. Schaut euch die Probeklausur also möglichst nicht an, bevor ihr die Probeklausur im Tutorium schreibt.

Probeklausur: (Revision r44)
Probeklausur Informatik 2 SS2005
Lösungshinweise zur Probeklausur Informatik 2 SS2005

Beim Vorbereiten der Probeklausur sind einige Aufgaben entstanden, die nicht in die Probeklausur übernommen wurden, da sonst der Umfang der Probeklausur weit über 60 min liegen würde. Diese Aufgaben können zum Üben benutzt werden.

Zusätzliche Übungsaufgaben: (Special Director's Cut Limited Edition) (Revision r44)
Übungsaufgaben
Lösungshinweise zu den Übungsaufgaben


Vortrag "Objekt-orientiertes Programmieren in C"

Posted on 2005-06-14 16:19 by Timo Bingmann at Permlink with 0 Comments. Tags: university talk c++

Im Sommersemester 2005 habe ich am Praktikum "Real-Life Programming" am IPD Lehrstuhl der UniKa teilgenommen. Hier platt die Beschreibung von der Homepage zitiert:

Wie programmiert man richtig?

Viele performancekritische Software wird immer noch in C geschrieben. C erlaubt dem Compiler einen sehr großen Optimierungsspielraum, in diesem Praktikum wird geübt, wie dieser ausgenutzt werden kann und wie die dabei auftretenden Klippen zu umschiffen sind.

In diesem Kontext könnt ihr lernen:

  • Den Umgang mit den UNIX Entwicklungswerkzeugen
  • Schreiben von portablem Code
  • Verständnis des Übersetzungsprozesses von C
  • Analysieren des durch Übersetzer erzeugten Assemblertextes
  • Programmieren, so dass der Übersetzer guten Code erzeugen kann
  • Wie man die Performance von Programmen steigern kann
  • Umgang mit großen Projekten
  • Das Finden von Fehlern in großen und alten Softwaresystemen
  • Beherrschen von Debugging und Profiling Werkzeugen
  • Kniffe des C-Präprozessors
  • Die "Geheimnisse" von C

In diesem Zusammenhang haben zwei Komilitonen und ich einen Vortrag über "Objekt-orientiertes Programmieren in C" (ohne ++) ausgearbeitet und gehalten. Weiteres Schwerpunktthema war die Darstellung von C++ in Maschine, also wie der C++ Übersetzer dann die Klassen abbildet.

Vortragsfolien: OOC-Folien.pdf 179 kB
Handout: OOC-Handout.pdf 122 kB
Beispielcode: OOC-Beispiele.tar.gz 4 kB

Hier noch ein Auszug des Inhaltsverzeichnisses:

  1. Objekt-Orientierte Konzepte
  2. OO in C
    • Kapselung und Geheimnisprinzip
    • Vererbung und Polymorphie
    • Generiztiät
  3. Darstellung von C++ in Maschine
    • vtable
    • Name-Mangling
    • Run-Time-Type Information (RTTI)

Diese Folien geben einen kompetenten Überblick über den Themenbereich.


RSS 2.0 Weblog Feed Atom 1.0 Weblog Feed Valid XHTML 1.1 Valid CSS (2.1)
Copyright 2005-2014 Timo Bingmann - Impressum