Seminario Interdipartimentale di Algoritmica
 
 

DI - Dipartimento di Informatica, via Salaria 113
Seminar Room, third floor

Abstract:

The talk aims to present certain JAVA applets for algorithm visualization developed within the project Algovision at the Charles University in Prague. Unlike most algorithm animations abundant at the web, we are trying to visualize not only "how", but also "why" algorithms work, which often means displaying situation so that invariants used in the correctness, termination, and complexity proofs are emphasized; in certain cases the complexity of the computation or design can be shown in a static way etc.
General ideas will be illustrated at the following algorithms:

Fast Fourier Transform - pointing out the main idea, static complexity presentation
Bellman-Ford shortest path algorithm - principal invariant visualization
Voronoi diagram (Fortune's algorithm) - presentation using cones
bitonic sort - a mathematical proof implemented as balanced and unbalanced tree data structures
- complexity shown for large objects.

The program Algovision, now under intensive development, involves other applets from different part of computers science, e.g. data structures, computer arithmetic (carry look-ahead addition), graph theory and combinatorial optimization (paths, spanning trees, network flows), computational geometry (convex hull) etc.