Posted on 2019-06-19 19:00 by Timo Bingmann at Permlink with 0 Comments. Tags: dissertation university

Today was the **ceremonial graduation day** on which new bachelors, masters, and also Dr.s (PhDs in the Anglo-Saxon world) were celebrated who received their degrees from the department of informatics at the Karlsruhe Institute of Technology (KIT) within the last year. This year's graduation day coincided with the **50th anniversary of the introduction of computer science** as a field of study and as a diploma degree.

I was among those honoured for completing the Dr. last year, (see my dissertation page). In total 44 freshly minted Dr.s, 292 masters, and 261 bachelors where celebrated today.

Furthermore, I was awarded the **Uniserv Research-Prize "Algorithms for Efficient Data-Processing"** for the **best dissertation in the field of fast algorithms** in the academic year 2017/2018 at the KIT department of informatics by the talent committee of the department.

I would like to **thank Uniserv** for endowing the department and my dissertation with this prize and the **especially the talent committee for selecting my work**. It was a great and pleasant surprise to receive such a notification in the morning email inbox, which as usual contained many "prize and distant inheritance" emails. But on that day one of them was real, and I nearly overlooked it.

My dissertation was the central purpose in my life for many years, and receiving the prize helps me feel the time was well spent and consider it as confirmation of having furthered the field of informatics a tiny bit. It is rare to receive such honours and I am truly grateful.

Posted on 2018-07-03 18:00 by Timo Bingmann at Permlink with 1 Comments. Tags: talk university dissertation frontpage

The road to a Dr. title (PhD in the Anglo-Saxon world) is often long, rough, and twisted. First you have to do original research, produce novel results, publish articles, and then write and ultimately publish a dissertation. Defending your research in the dissertation in front of a panel of professors is one of the final milestones on that journey.

On July 3rd, I successfully defended my dissertation at the Karlsruhe Institute of Technology and the dissertation text has now been published as a book.

My final dissertation PDF is available here: dissertation-Bingmann-Scalable-String-and-Suffix-Sorting.pdf .

It has also been published at the KIT library, on arXiv:1808.00963, and finally as a print-on-demand paperback from Amazon.

The published book cover's background shows a list of most common words in the Wikipedia. The words are sorted and their distinguishing prefix is marked in blue. The cover is available as a double-page PDF: dissertation-cover.pdf , and as front and back separately: dissertation-cover-front.pdf and dissertation-cover-back.pdf .

The LaTeX source code for my dissertation is available for download: dissertation-source.zip (791 KiB). The complete text is in one `.tex`

file, all figures (except the creative commons logo) are generated from the LaTeX code.

The slides of my presentation during the defense are available for download here: dissertation-defense-slides.pdf .

The presentation was only part of the whole defense. My actual slide set also had almost 200 more backup slides, which however were collected from all the other talks already available on this homepage. These backup slides helped greatly in the examination question after the presentation.

Posted on 2016-01-14 18:30 by Timo Bingmann at Permlink with 0 Comments. Tags: maths university frontpage

After a long exhausting period with many interruptions my diploma thesis in mathematics "**On the Structure of the Graph of Unique Symmetric Base Exchanges of Bispanning Graphs**" is finalized and submitted. The full abstract of the thesis is shown below, and an additional German abstract is available further down the page.

The final version of the thesis is available here: **thesis pdf **, and was also uploaded to arXiv.org as 1601.03526.

The underlying problem discussed in the thesis is best explained using **a game on a bispanning graph**. You can **play the game with this Java Applet** or using the **Java WebStart Launcher** (if the Applet does not work). You play Alice's role and want to flip the colors of all edges in the graph. Bob will try to prevent this from happening.

In addition to the thesis itself, the source code of the accompanying computer program is also available. It was used while preparing the thesis to calculate exchanges graphs and to test many hypothesis about bispanning graphs. The program can **enumerate all bispanning graphs and their exchange graphs** for small numbers of vertices. See the program page for downloadable lists and PDFs of all bispanning graphs for small numbers of vertices.

Bispanning graphs are undirected graphs with an edge set that can be decomposed into two disjoint spanning trees. The operation of symmetrically swapping two edges between the trees, such that the result is a different pair of disjoint spanning trees, is called an edge exchange or a symmetric base exchange. The graph of symmetric base exchanges of a bispanning graph contains a vertex for every valid pair of disjoint spanning trees, and edges between them to represent all possible edge exchanges. We are interested in a restriction of these graphs to only unique symmetric base exchanges, which are edge exchanges wherein selecting one edge leaves only one choice for selecting the other. In this thesis, we discuss the structure of the graph of unique symmetric edge exchanges, and the open question whether these are connected for all bispanning graphs.

This abstract problem can be nicely rephrased into a coloring game with two players: Alice and Bob are given a bispanning graph colored with two disjoint spanning trees, and Alice gets to flip the color of any edge. This creates a cycle in one color and a cut in the other, and Bob must then flip a different edge to repair the constraint that both colors represent disjoint spanning trees. Alice's objective is to invert the color of all edges in the graph, and Bob's to prevent this. We are interested in whether Alice can find a sequence of unique edge exchanges for any bispanning graph, since these leave Bob no choice in which edge to select, hence allowing Alice to win with certainty.

In this thesis, we first define and discuss the properties of bispanning graphs in depth. Intuitively, these are locally dense enough to allow the two disjoint spanning trees to reach all vertices, but sparse enough such that disjoint edge sets do not contain cycles. The whole class of bispanning graphs can be inductively constructed using only two operations, which makes the class tractable for inductive proofs.

We then describe in detail directed, undirected, and simplified versions of edge exchange graphs, first with unrestricted edge exchanges, and then with the restriction to unique symmetric base exchanges. These exchange graphs are related to a set of conjectures put forth by White in 1980 on base exchanges in matroids, and also to conjectures on cyclic base orderings of matroids. To date, these conjectures have not been proven in full generality, despite overwhelming computational evidence.

As steps towards showing the conjecture that the graph of unique symmetric base exchanges is connected for all bispanning graphs, we prove a composition method to construct the unique exchange graph of any bispanning graph from the exchange graphs of smaller bispanning graphs. Furthermore, using a computer program developed alongside this thesis, we are able to enumerate and make statements about all small bispanning graphs and their exchanges graphs.

Our composition method classifies bispanning graphs by whether they contain a non-trivial bispanning subgraph, and by vertex and edge connectivity. For bispanning graphs containing a non-trivial bispanning subgraph, we prove that the unique exchange graph is the Cartesian graph product of two smaller exchange graphs. For 2-vertex-connected bispanning graphs, we show that the bispanning graph is the 2-clique sum of two smaller bispanning graphs, and that the unique exchange graph can be built by joining their exchange graphs and forwarding edges at the join seam. And for all remaining bispanning graphs, we prove a composition method at a vertex of degree three, wherein the unique exchange graph is constructed from the exchange graphs of three reduced bispanning graphs.

We conclude this thesis with ideas and evidence for future approaches to proving the connectivity of the unique exchange graphs and show the most difficult bispanning graphs instances.

Posted on 2015-09-22 15:46 by Timo Bingmann at Permlink with 0 Comments. Tags: research sorting university

Our paper "**Engineering Parallel String Sorting**" was accepted for publication in Springer's Algorithmica Journal, and is available online at http://dx.doi.org/10.1007/s00453-015-0071-1.

Compare to our older technical report, the journal edition contains many (minor and major) corrections, additional references and better explanations.

A pre-print version is available here: Engineering-Parallel-String-Sorting.pdf .

Please refer to the main parallel-string-sorting page for details and source code.

Posted on 2014-10-29 11:17 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.

More history about STXXL can be found in the blog post to 1.4.0. Today, the second release of the new 1.4 branch was published:

What's new in 1.4.1 ?

- Integrated support for kernel based asynchronous I/O on Linux (new file type "
`linuxaio`

"), which exploits Native Command Queuing (NCQ) if available. - Merged
`stxxl::unordered_map`

branch, which provides a hash map backed by external memory. - Replaced
`struct default_completion_handler`

with a`NULL`

pointer, thus avoiding superfluous new/delete work for each I/O request. - Added
`stxxl::external_shared_ptr`

which is a proxy class to allow use of shared_ptr classes inside stxxl containers. - Fixing bugs and warnings on 32-bit systems (yes, they still exist).
- Use
`atomic_counted_object`

in class file for request reference counting. - Adding support for MinGW-w64 (64-bit) systems with working SJLJ thread implementations.

See the CHANGELOG for further minor changes.

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 ?

- reorganized source hierarchy into include/ lib/ tests/ examples/ doc/ tools/
- CMake build system for cross-platform compilation
- greatly improved documentation with tutorials and examples
- efficient external matrix operations
- new containers
`stxxl::sequence`

and`stxxl::sorter`

- improved .stxxl disk configuration files and additional options
- combined stxxl_tool of disk benchmarks
- simple examples and skew3 as real-world stream application
- support for Visual Studio 2012 and 2013
*without*Boost - important bug fixes in
`stxxl::queue`

and`stxxl::priority_queue`

Posted on 2013-05-22 23:50 by Timo Bingmann at Permlink with 2 Comments. Tags: c++ university fun sorting sound of 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.

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:

- Polynomial classes for monomial and Bézier representations: PolynomialStandard and PolynomialBezier.
- Algorithms to convert from monomial to Bézier representation and vice versa: PolynomialStandard::toBezier() and PolynomialBezier::toStandard().
- Evaluation algorithms for both representations: Horner's Schema and the Algorithm of de Casteljau.
- Another version of de Casteljau's Algorithm to split a polynomial in Bézier representation into two parts.
- Jarvis' March aka gift wrapping (run time O(hn)) to calculate the convex hull of the Bézier polygon: PolynomialBezier::getConvexHull().
- Cardano's formulas to find all real roots of any cubic polynomial: PolynomialStandard::findRoots().

For the lab course I wrote two documents, both in German: one is an abstract Kurzfassung.pdf (1 page), which is translated into English below, and the other a short report 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 , which however are not self-explanatory due to my minimum-text presentation style.

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 (2.79 MiB).

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 führt zur Definition von Differenzenmengen und beide Ergebnisse liefern elegante Konstruktionsverfahren für .

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:

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.

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:

- ns-3 Basics
- Introduction
- Showcase: Design Patterns
- Current State

- Wifi in ns-3
- State of 802.11
- PHY Layer
- Signals, Noise and Interference
- Short Recapitulation of DCF
- QoS with EDCA

- Conclusion

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.

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)

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.

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/.

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:

SVG | SVG (Inkscape) | EPS | ||

SVG | SVG (Inkscape) | EPS |

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

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.

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:

- An initial root task,
- a pager (memory server and task server combined) creating virtual address spaces,
- a root name server for servers to register their facilities,
- a minix file system server which extends the name space to files,
- a (virtual) console server reading keyboard input and writing to the screen buffer,
- and a limited shell with two utility programs: ls and cat.

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!

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.

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.

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.

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:

- Goals
- Name Catalogs
- Object Representation
- Catalogs

- IDL Interfaces
- Resolve Interface
- Bind Interface

- Extension / Ideas

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.

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

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:

- Objekt-Orientierte Konzepte
- OO in C
- Kapselung und Geheimnisprinzip
- Vererbung und Polymorphie
- Generiztiät

- Darstellung von C++ in Maschine
- vtable
- Name-Mangling
- Run-Time-Type Information (RTTI)

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