Mathematical and Engineering Methods in Computer Science

A key issue in VoIP services market is the availability of tools that permit a constant monitoring of the relevant Quality of Service (QoS) parameters. Several commercial and open-source solutions are available, based on dedicated hardware and/or open-source software. These solutions aim to achieve a tradeoff between performance and instrumentation cost. In general, high performance and precise monitoring tools are based on dedicated hardware, which is expensive. In contrast, cheaper software-based solutions working on top of a Commercially available Off-The-Shelf (COTS) hardware are performance-limited, especially when serving high-capacity links. In this context, the paper presents an open-source solution for QoS monitoring of VoIP traffic that achieves high performance at significantly lower costs. The proposed solution exploits the performance capabilities achievable with a field-programmable gate array (FPGA). The associated costs reduction arises from the high flexibility of an FPGA. Our experimental analysis explores the accuracy of the developed prototype, measuring against relevant QoS parameters of VoIP traffic on high capacity links.

Automatic Speech Recognition (ASR) is pervading nowadays to areas unimaginable a few years ago. This progress was achieved mainly due to massive changes in the “Smart phones world” and ubiquitous availability of small, and powerful Linux-based hardware.

Recently, the availability of free ASR systems with acceptable speed and accuracy performance grew. Together with the changes the mobile world brought, a developer is now able to include ASR quickly without detailed knowledge of the underlying technology. What will be the future of embedded ASR systems in this case?

This talk presents two embedded ASR applications and points out their advantages over today’s quick solutions. The first one demonstrates how changes in users behavior allowed to design a usable voice enabled house control. The second one is an extremely reliable in–car real–time ASR system which can even use a remote ASR for complex tasks.

Actual software in use today is not known to follow any uniform normal distribution, whether syntactically—in the language of all programs described by the grammar of a given programming language, or semantically—for example, in the set of reachable states. Hence claims deduced from any given set of benchmarks need not extend to real-world software systems.

When building software analysis tools, this affects all aspects of tool construction: starting from language front ends not being able to parse and process real-world programs, over inappropriate assumptions about (non-)scalability, to failing to meet actual needs of software developers.

To narrow the gap between real-world software demands and software analysis tool construction, an experiment using the Debian Linux distribution has been set up. The Debian distribution presently comprises of more than \(22000\) source software packages. Focussing on C source code, more than \(400\) million lines of code are automatically analysed in this experiment, resulting in a number of improvements in analysis tools on the one hand, but also more than \(700\) public bug reports to date.

A central task in biomedical image analysis is the segmentation and quantification of 3D image structures. A large variety of segmentation approaches have been proposed including approaches based on different types of deformable models. A main advantage of deformable models is that they allow incorporating a priori information about the considered image structures. In this contribution we give a brief overview of often used deformable models such as active contour models, statistical shape models, and analytic parametric models. Moreover, we present in more detail 3D analytic parametric intensity models, which enable accurate and robust segmentation and quantification of 3D image structures. Such parametric models have been successfully used in different biomedical applications, for example, for the localization of 3D anatomical point landmarks in 3D MR and CT images, for the quantification of vessels in 3D MRA and CTA images, as well as for the segmentation of cells and subcellular structures in 3D microscopy images.

The correctness of parallel and reactive programs is often easier specified using formulae of temporal logics. Yet verifying that a system satisfies such specifications is more difficult than verifying safety properties: the recurrence of a specific program state has to be detected. This paper reports on the development of a generic framework for automatic verification of linear temporal logic specifications for programs in LLVM bitcode. Our method searches explicitly through all possible interleavings of parallel threads (control non-determinism) but represents symbolically the variable evaluations (data non-determinism), guided by the specification in order to prove the correctness. To evaluate the framework we compare our method with state-of-the-art tools on a set of unmodified C programs.

We consider the currently strongest Steiner tree approximation algorithm that has recently been published by Goemans, Olver, Rothvoß and Zenklusen (2012). It first solves a hypergraphic LP relaxation and then applies matroid theory to obtain an integral solution. The cost of the resulting Steiner tree is at most \((1.39 + \varepsilon )\)-times the cost of an optimal Steiner tree where \(\varepsilon \) tends to zero as some parameter \(k\) tends to infinity. However, the degree of the polynomial running time depends on this constant \(k\), so only small \(k\) are tractable in practice.

The algorithm has, to our knowledge, not been implemented and evaluated in practice before. We investigate different implementation aspects and parameter choices of the algorithm and compare tuned variants to an exact LP-based algorithm as well as to fast and simple \(2\)-approximations.

Transactional memory (TM) is an increasingly popular technique for synchronising threads in multi-threaded programs. To address both correctness and performance-related issues of TM programs, one needs to monitor and analyse their execution. However, monitoring concurrent programs (including TM programs) may have a non-negligible impact on their behaviour, which may hamper the objectives of the intended analysis. In this paper, we propose several approaches for monitoring TM programs and study their impact on the behaviour of the monitored programs. The considered approaches range from specialised lightweight monitoring to generic heavyweight monitoring. The implemented monitoring tools are publicly available to the scientific community, and the implementation techniques used for lightweight monitoring of TM programs may be used as an inspiration for developing other specialised lightweight monitors.

A new approach to synthesize bent Boolean functions by means of Cartesian Genetic Programming (CGP) has been proposed recently. Bent functions have important applications in cryptography due to their high nonlinearity. However, they are very rare and their discovery using conventional brute force methods is not efficient enough. In this paper, a new parallel implementation is proposed and the performance is evaluated on the Intel Xeon Phi Coprocessor.

The 3D fast Fourier transform (FFT) is the heart of many simulation methods. Although the efficient parallelisation of the FFT has been deeply studied over last few decades, many researchers only focused on either pure message passing (MPI) or shared memory (OpenMP) implementations. Unfortunately, pure MPI approaches cannot exploit the shared memory within the cluster node and the OpenMP cannot scale over multiple nodes.

This paper proposes a 2D hybrid decomposition of the 3D FFT where the domain is decomposed over the first axis by means of MPI while over the second axis by means of OpenMP. The performance of the proposed method is thoroughly compared with the state of the art libraries (FFTW, PFFT, P3DFFT) on three supercomputer systems with up to 16k cores. The experimental results show that the hybrid implementation offers 10-20% higher performance and better scaling especially for high core counts.

Construction of a mapping between educational content and skills is an important part of development of adaptive educational systems. This task is difficult, requires a domain expert, and any mistakes in the mapping may hinder the potential of an educational system. In this work we study techniques for improving a problem-skill mapping constructed by a domain expert using student data, particularly problem solving times. We describe and compare different techniques for the task – a multidimensional model of problem solving times and supervised classification techniques. In the evaluation we focus on surveying situations where the combination of expert opinion with student data is most useful.

One of the important areas of current cellular research with substantial impacts on medicine is analyzing the spatial organization of genetic material within the cell nuclei. Higher-order chromatin structure has been shown to play essential roles in regulating fundamental cellular processes, like DNA transcription, replication, and repair. In this paper, we present an image analysis method for the localization of gene loci with regard to chromosomal territories they occupy in 3D confocal microscopy images. We show that the segmentation of the territories to obtain a precise position of the gene relative to a hard territory boundary may lead to undesirable bias in the results; instead, we propose an approach based on the evaluation of the relative chromatin density at the site of the gene loci. This method yields softer, fuzzier “boundaries”, characterized by progressively decreasing chromatin density. The method therefore focuses on the extent to which the signals are located inside the territories, rather than a hard yes/no classification.

In online scheduling problems, we want to assign jobs to machines while optimizing some given objective function. In the class we study in this paper, we are given a number \(m\) of machines and two jobs that both want to use each of the given machines exactly once in some predefined order. Each job consists of \(m\) tasks and each task needs to be processed on one particular machine. The objective is to assign the tasks to the machines while minimizing the makespan, i.e., the processing time of the job that takes longer. In our model, the tasks arrive in consecutive time steps and an algorithm must assign a task to a machine without having full knowledge of the order in which the remaining tasks arrive. We study the advice complexity of this problem, which is a tool to measure the amount of information necessary to achieve a certain output quality. A great deal of research has been carried out in this field; however, this paper studies the problem in a new setting. In this setting, the oracle does not know the exact future anymore but only all possible future scenarios and their probabilities. This way, the additional information becomes more realistic. We prove that the problem is more difficult with this oracle than before. Moreover, in job shop scheduling, we provide a lower bound of \(1+1/(6\sqrt{m})\) on the competitive ratio of any online algorithm with advice and prove an upper bound of \(1+1/\sqrt{m}\) on the competitive ratio of an algorithm from Hromkovič et al. [8].