RISC-Linz RISC-Linz Research Institute for Symbolic Computation  

Bachelor-Seminar Selected Algorithms in Symbolic Computation

Description - Course Details - Schedule - History


The main objective of this seminar is to discuss algorithms in Symbolic Computation with the possibility to write a bachelor thesis in the framework of this seminar. The seminar is devoted to the study of elegant, efficient, practial, interesting, classical and non-classical algorithms. The main emphasis will be put on algorithms that are typically not covered by introductory lectures or textbooks on algorithms, but which nevertheless are of general interest. Also little-known aspects of well-known algorithms are potential topics of the seminar.

Algorithms from various areas will be discussed. For instance:

Typically, at each meeting there will be a self-contained presentation of some algorithm. Depending on the algorithm and on the interest of the audience, the focus of the discussion might be on complexity analysis, comparison to related algorithms, data structures, implementation details, or applications.


Course Details

Course ID: 326.006
If you are JKU student, please register to this course via KUSSS.
Organizers: Manuel Kauers, Temur Kutsia, Veronika Pillwein and Carsten Schneider
Time: Thursday, 17.15-18.45 (if participants prefer an earlier slot, we can try to find a more convenient time in the first meeting)
First meeting: March 15
Place: HS 11
Prerequesits: Participants are expected to be familiar with fundamental algorithms as taught in introductory courses such as 326.011 by Carsten Schneider or 326.026 by Heinrich Rolletschek.


Schedule (Summer 2012)

Date Speaker Title Abstract
2012-03-15 Temur Kutsia Contejean-Devie Algorithm for Solving Systems of Linear Diophantine Equations The Contejean-Devie algorithm solves systems of linear Diophantine equations over natural numbers. It is a generalization of Fortenbacher's algorithm for solving one equation. In this talk we present the Contejean-Devie algorithm for homogeneous systems of linear Diophantine equations, discuss its properties, its relation with Fortenbacher's algorithm, show on an example how it works and indicate how inhomogeneous systems can be solved. [slides]
2012-03-22 Manuel Kauers Generating Random Structures First we give a few remarks on the generation of random bits, and how to use them to generate random integers between two given bounds a and b such that every number is equally likely to appear as output. This is trivial when the number of integers in the interval is a power of two, but somewhat more subtle when it is not. In the second part, we show how to pick efficiently a random element from a finite (but large) collection of combinatorial objects (e.g. trees), using efficiently computable bijections between a range of integers and the set of combinatorial objects. [slides]
2012-03-22 Veronika Pillwein Rational parametrization of algebraic curves
(An appetizer)
Algebraic curves can be represented implicitly using their defining polynomial. This representation is well suited for checking whether a particular given point is on the curve, but it is not the best description, if a set of points on the given curve shall be generated, e.g., for the purpose of plotting. In this talk, we give an introduction to rational parametrization, i.e., we discuss criteria when an algebraic curve is rationally parametrizable and show how to compute such a parametrization for some sample cases. [slides]
2012-03-29 Carsten Schneider Heap Sort In this presentation we work out the general principles of HeapSort. Starting with binary trees we specialize them to heap trees which are completely filled and which have the heap property (the elements in a node are not smaller than the elements in the sub-nodes). This property guarantees that the insertion of an element in such a tree with n elements can be carried out in O(log(n)) time. In particular, the maximum can be extracted and deleted in O(log(n)) time. This gives a straightforward sorting algorithm for a given set of n elements: construct a heap tree in O(n log(n)) time; afterwards, extract and delete iteratively always the maximum. In this way, one gets the sorted list (in reversed order) in O(n log(n)) time. HeapSort for arrays models this idea by encoding the tree in the array in a straightforward manner. In contrast to MergeSort, we obtain a worst case sorting algorithm in O(n log(n)) time which works in place (i.e., it requires only the input array as basic memory). Variants of HeapSort are mentioned (for possible further considerations) that work faster than QuickSort if the input size is large enough. [blackboard]
2012-05-31 Paul Gschoepf String matching
2012-06-14 no show
2012-06-21 Johannes Nigl Combinatorial Bijections
2012-06-28 Stefan Zweckinger Factorization and Pollard-Rho



Seminar program of earlier years: