panthema / tags / frontpage
Book Cover of Dissertation

Dissertation "Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools"

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.

Published Dissertation

My final dissertation PDF is available here: dissertation-Bingmann-Scalable-String-and-Suffix-Sorting.pdf 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 dissertation-cover.pdf, and as front and back separately: dissertation-cover-front.pdf dissertation-cover-front.pdf and dissertation-cover-back.pdf dissertation-cover-back.pdf.

The LaTeX source code for my dissertation is available for download: dissertation-source.zip 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.

Dissertation Defense Presentation

The slides of my presentation during the defense are available for download here: dissertation-defense-slides.pdf 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.

Download dissertation-defense-slides.pdf
This blog entry continues on the next page ...

Sketch of a edge-split-attach operation, which breaks a unique exchange from e.

"On the Structure of the Graph of Unique Symmetric Base Exchanges of Bispanning Graphs" - Diploma Thesis in Mathematics

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 Bingmann-On-the-Structure-of-the-Graph-of-Unique-Symmetric-Base-Exchanges-of-Bispanning-Graphs.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.

Abstract

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.

This blog entry continues on the next page ...

Screenshot of YouTube View Counter of the "15 Sorting Algorithms in 6 Minutes"

1.000.000 Views of Sound of Sorting YouTube Video

Posted on 2014-10-26 17:30 by Timo Bingmann at Permlink with 1 Comments. Tags: sorting sound of sorting frontpage

Some time last week my YouTube video "15 Sorting Algorithms in 6 Minutes" reached 1 million views. The original video was uploaded on 2013-05-20 which is just 524 days ago, so on average about every 45.2 seconds someone started to watch the video (which itself is about 6 minutes long). The world is a really big place. Most of the views, however, occured in spikes of interest, as seen in the graph below.

The original video contained only 15 algorithms. The program "Sound of Sorting" itself, which was used to create the animations, now contains 30 algorithms or variants. For some of the additional algorithms I also created videos on YouTube, which are also worthwhile watching.

There are two parallel algorithms based on sorting networks, where each left-to-right sweep is one parallel sorting step:

An algorithm, which is optimal in terms of the number of writes to sort the array:

An adaptive sorting algorithm which detects presorted areas, and is used in many modern programming language runtime libraries:

An in-place stable mergesort with O(1) extra space:

And two algorithms, that have a high asymptotic worst-case complexity, and are thus more a joke, but still pretty to watch:

This blog entry continues on the next page ...

First slide of the talk showing the inside of a hard disk

Recording of a Talk "STXXL 1.4.0 and Beyond"

Posted on 2014-06-22 20:00 by Timo Bingmann at Permlink with 0 Comments. Tags: c++ stxxl talk frontpage

This is a recording of a talk that I gave last week at the 3rd LSDMA Topical Meeting in Berlin. The talk covers a basic introduction into the STXXL library's features and contains many short code examples that serve as a tutorial.

The slides of the presentation 2014-06-22 STXXL 1.4.0 and Beyond.pdf 2014-06-22 STXXL 1.4.0 and Beyond.pdf are available online and the recorded talk can be seen on Youtube video below.

Download 2014-06-22 STXXL 1.4.0 and Beyond.pdf

And here is the video of the recording: https://www.youtube.com/watch?v=UswxcAOJKBE

This blog entry continues on the next page ...

Screenshot of KIT Informatik Webpage

Sound of Sorting: Viral Video on KIT Informatik Webpage

Posted on 2013-10-24 22:45 by Timo Bingmann at Permlink with 0 Comments. Tags: fun sorting sound of sorting frontpage

Little did I expect what would happen when coding the Sound of Sorting demo program. The initial motivation was to create a program that counts the number of comparisons of sorting algorithms, so that the students in our lecture "Algorithms 1" could compare the results of theoretical analysis and real implementations. There were many programs similar to the one I finally made, but there was no program in which the sorting algorithms were easily readable, and not entwined with visualization code. I needed the third-year students to see "simple" code and at the same time have comparison counting and nice visualizations. And none of the existing programs highlighted the internal workings of the algorithms well.

These were the initial goals what became the Sound of Sorting. The program itself took only about seven days of coding work, which was done from the 17th to 21st of May this year. The program had to be finished for the lecture on the 22nd, so there was a hard deadline to meet. The videos were created on the following weekends, and additional algorithms were added later.

Adding sound effects was very much an afterthought, because I had done some similar work previously with manipulating waveforms. Thus there was no learning curve to overcome to have comparisons play sounds. What kind of sound to play, however, needed a lot of artistic touch, trial and error, and the ability to map and transform frequency, oscillators and envelopes as needed. Forming, mixing and bending sound waves as done in the Sound of Sorting requires a mathematical mindset and some appropriate background.

The by-product of this demo program for teaching sort algorithms was the YouTube video "15 Sorting Algorithms in 6 Minutes" which, to my great surprise, went viral on social networks and was viewed 420.000 times to-date. I'm glad that many people with otherwise no connections to algorithmics find this video interesting, and hope that those with further interest view the slower videos, which provide more insight into the algorithms.

Today, the video infected the front page of my current employer: the Department of Informatics at the Karlsruhe Institute of Technology (KIT), which is of course whom I originally made the demo program for. The text, which I wrote for that occasion, can be viewed in German at the original news article about the viral video (or in the screenshots below). I have translated it into English below, since it contains some further comments about the video.

This blog entry continues on the next page ...

Photo of my Raspberry Pi Model B

STX B+ Tree Speed Test Measurements on Raspberry Pi (Model B)

Posted on 2013-05-06 09:48 by Timo Bingmann at Permlink with 1 Comments. Tags: stx-btree frontpage

The Raspberry Pi is maybe one of the most hyped embedded system projects in the last year, and I also got myself one for experiments. People are doing amazing things with this Linux-in-a-box SoC. Doubtlessly, the popularity is due to the standardized platform and a large community forming around it, which makes fixing the many small problems with Linux on ARM systems feasible. For me, the Raspberry Pi is an alternative architecture on which to test my algorithms and libraries, which exhibits somewhat different characteristics than the highly optimized desktop CPUs.

So I decided to run my STX B+ Tree speed test on the Raspberry Pi Model B, because most people use the SoC for multimedia purposes and little other memory performance data is available. The B+ tree speed test gives insight into the platform's overall memory and processing performance, and thus yields a better assessment of how useful the system is for general purpose applications (unlike multimedia decoding). Most benchmarks focus solely on floating point or integer arithmetic, which alone are very poor indicators for overall system performance. The Raspberry Pi forums say it has performance similar to a "Pentium 2 with 300 MHz", but that is for arithmetic.

This blog entry continues on the next page ...

STX B+ Tree Measuring Memory Usage with malloc_count

Posted on 2013-05-05 09:44 by Timo Bingmann at Permlink with 2 Comments. Tags: stx-btree frontpage

Within the next few days, a new version of my popular STX B+ Tree library will be released. In light of this imminent release, I created a memory profile with my malloc_count tool, comparing the requirements of four different C++ maps with integer keys and values.

The test is really simple: create a map container, insert 8 Mi random integer key/value pairs, and destruct it. The memory profile shows the amount of memory over time as allocated via malloc() or new. The test encompasses the usual gcc STL's map which is a red-black tree, the older hash_map from gcc's STL extensions, the newer gcc C++ tr1::unordered_map, and of course the stx::btree_map with default configuration. As a reference, I also added the usual STL vector and deque (not map containers), to verify the plotting facilities.

To isolate heap fragmentation, the profiler fork()s separate process contexts before each run. To avoid problems with multiple equal random keys, the multimap variant of all containers is used. Here is the memory profile (also included in the STX B+ Tree tarball):

Memory profile of map containers

This blog entry continues on the next page ...

Instacode coloring of assembler code

Coding Tricks 101: How to Save the Assembler Code Generated by GCC

Posted on 2013-01-24 18:07 by Timo Bingmann at Permlink with 2 Comments. Tags: c++ coding tricks frontpage

This is the first issue of a series of blog posts about some Linux coding tricks I have collected in the last few years.

Folklore says that compilers are among the most complex computer programs written today. They incorporate many optimization algorithms, inline functions and fold constant expressions; all without changing output, correctness or side effects of the code. If you think about it, the work gcc, llvm and other compilers do is really amazing and mostly works just great.

Sometimes, however, you want to know exactly what a compiler does with your C/C++ code. Most straight-forward questions can be answered using a debugger. However, if you want to verify whether the compiler really applies those optimizations to your program, that your intuition expects it to do, then a debugger is usually not useful, because optimized programs can look very different from the original. Some example questions are:

These questions can be answered definitely by investigating the compiler's output. On the Net, there are multiple "online compilers," which can visualize the assembler output of popular compilers for small pieces of code: see the "GCC Explorer" or "C/C++ to Assembly v2". However, for inspecting parts of a larger project, these tools are unusable, because the interesting pieces are embedded in much larger source files.

Luckily, gcc does not output binary machine code directly. Instead, it internally writes assembler code, which then is translated by as into binary machine code (actually, gcc creates more intermediate structures). This internal assembler code can be outputted to a file, with some annotation to make it easier to read.

This blog entry continues on the next page ...

Instacode coloring of stacktrace

C++ Code Snippet - Print Stack Backtrace Programmatically with Demangled Function Names

Posted on 2008-09-01 22:30 by Timo Bingmann at Permlink with 34 Comments. Tags: c++ code-snippet coding tricks frontpage

Yesterday I was tasked to analyzed an inner function of a reasonably complex software package. The inner function was called thousands of times from many different parts of the program, a simple counter print-out showed that. However I was interested in which execution paths reach this inner function and how often the different parts access the function.

My straight-forward idea was to dump a stack backtrace each time the inner function is called, similar to the one printed by a debugger. However I needed some code snippet to dump the stack backtrace programmatically, without using gdb to halt the program each time.

Stack backtraces can be saved with backtrace(3), resolved into symbolic names using backtrace_symbols(3) and printed using backtrace_symbols_fd(3). These functions are well documented and fairly easy to use.

However I was debugging a C++ program, which made heavy use of templates and classes. C++ symbols names (including namespace, class and parameters) are mangled by the compiler into plain text symbols: e.g. the function N::A<int>::B::func(int) becomes the symbol _ZN1N1AIiE1B4funcEi. This makes the standard backtrace output very unreadable for C++ programs.

To demangle these strings the GNU libstdc++ library (integrated into the GNU Compiler Collection) provides a function called __cxa_demangle(). Combined with backtrace(3) a pretty stack backtrace can be outputted. The demangling function only works for programs compiled with g++.

The following header file contains a function print_stacktrace(), which uses backtrace(3), backtrace_symbols(3) and __cxa_demangle() to print a readable C++ stack backtrace.

This blog entry continues on the next page ...

C++ Code Snippet - Compressing STL Strings with zlib

Posted on 2007-03-28 18:23 by Timo Bingmann at Permlink with 11 Comments. Tags: c++ code-snippet frontpage

The zlib library can be found on virtually every computer. It is THE general-purpose lossless patent-free compression library.

This small C++ code snippet features a pair of functions which use this ubiquitous library to compress ordinary STL strings. There are many uses for this code snippet, like compressing string data stored in a database or binary data transfered over a network. Keep in mind that the compressed string data is binary, so the string's c_str() representation must be avoided.

To compile the following small program use "gcc testzlib.cc -o testzlib -lz" where testzlib.cc is the code.

// Copyright 2007 Timo Bingmann <tb@panthema.net>
// Distributed under the Boost Software License, Version 1.0.
// (See http://www.boost.org/LICENSE_1_0.txt)

#include <string>
#include <stdexcept>
#include <iostream>
#include <iomanip>
#include <sstream>

#include <zlib.h>

/** Compress a STL string using zlib with given compression level and return
  * the binary data. */
std::string compress_string(const std::string& str,
                            int compressionlevel = Z_BEST_COMPRESSION)
{
    z_stream zs;                        // z_stream is zlib's control structure
    memset(&zs, 0, sizeof(zs));

    if (deflateInit(&zs, compressionlevel) != Z_OK)
        throw(std::runtime_error("deflateInit failed while compressing."));

    zs.next_in = (Bytef*)str.data();
    zs.avail_in = str.size();           // set the z_stream's input

    int ret;
    char outbuffer[32768];
    std::string outstring;

    // retrieve the compressed bytes blockwise
    do {
        zs.next_out = reinterpret_cast<Bytef*>(outbuffer);
        zs.avail_out = sizeof(outbuffer);

        ret = deflate(&zs, Z_FINISH);

        if (outstring.size() < zs.total_out) {
            // append the block to the output string
            outstring.append(outbuffer,
                             zs.total_out - outstring.size());
        }
    } while (ret == Z_OK);

    deflateEnd(&zs);

    if (ret != Z_STREAM_END) {          // an error occurred that was not EOF
        std::ostringstream oss;
        oss << "Exception during zlib compression: (" << ret << ") " << zs.msg;
        throw(std::runtime_error(oss.str()));
    }

    return outstring;
}

/** Decompress an STL string using zlib and return the original data. */
std::string decompress_string(const std::string& str)
{
    z_stream zs;                        // z_stream is zlib's control structure
    memset(&zs, 0, sizeof(zs));

    if (inflateInit(&zs) != Z_OK)
        throw(std::runtime_error("inflateInit failed while decompressing."));

    zs.next_in = (Bytef*)str.data();
    zs.avail_in = str.size();

    int ret;
    char outbuffer[32768];
    std::string outstring;

    // get the decompressed bytes blockwise using repeated calls to inflate
    do {
        zs.next_out = reinterpret_cast<Bytef*>(outbuffer);
        zs.avail_out = sizeof(outbuffer);

        ret = inflate(&zs, 0);

        if (outstring.size() < zs.total_out) {
            outstring.append(outbuffer,
                             zs.total_out - outstring.size());
        }

    } while (ret == Z_OK);

    inflateEnd(&zs);

    if (ret != Z_STREAM_END) {          // an error occurred that was not EOF
        std::ostringstream oss;
        oss << "Exception during zlib decompression: (" << ret << ") "
            << zs.msg;
        throw(std::runtime_error(oss.str()));
    }

    return outstring;
}

/** Small dumb tool (de)compressing cin to cout. It holds all input in memory,
  * so don't use it for huge files. */
int main(int argc, char* argv[])
{
    std::string allinput;

    while (std::cin.good())     // read all input from cin
    {
        char inbuffer[32768];
        std::cin.read(inbuffer, sizeof(inbuffer));
        allinput.append(inbuffer, std::cin.gcount());
    }

    if (argc >= 2 && strcmp(argv[1], "-d") == 0)
    {
        std::string cstr = decompress_string( allinput );

        std::cerr << "Inflated data: "
                  << allinput.size() << " -> " << cstr.size()
                  << " (" << std::setprecision(1) << std::fixed
                  << ( ((float)cstr.size() / (float)allinput.size() - 1.0) * 100.0 )
                  << "% increase).\n";

        std::cout << cstr;
    }
    else
    {
        std::string cstr = compress_string( allinput );

        std::cerr << "Deflated data: "
                  << allinput.size() << " -> " << cstr.size()
                  << " (" << std::setprecision(1) << std::fixed
                  << ( (1.0 - (float)cstr.size() / (float)allinput.size()) * 100.0)
                  << "% saved).\n";

        std::cout << cstr;
    }
}

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