**
Low Degree Connectivity
in Ad-Hoc Networks***

**Charles
University, Prague**

__
Abstract__

The
aim of the paper is to investigate the average case behavior of certain
algorithms that are designed for connecting mobile agents in the two- or
three-dimensional space. The general model is the following: let *X* be a
set of points in the *d*-dimensional Euclidean space *E _{d}*,

Keywords: wireless network, radio network, power minimizing, probabilistic analysis, percolation theory

**
Algovision**

(visualization of algorithms)

A system of applets for algorithm visualization and teaching

The system covers the following algorithms:

**
Data Structures**:
binary search tree, AVL-tree, red&black tree, Btree

**
Sorting**:
mergesort, heapsort, quicksort, bubble sort, *O(N)* time median, bitonic
sorting

**
Graph Algorithms**:
different algorithms for shortest path, min spanning tree and network flows,
spectral heuristic for min-cut

**
Arithmetic Algorithms**:
carry look-ahead addition, fast Fourier transform

**
Geometric Algorithms**:
convex hull and Voronoi diagram in the plane

**
String Searching**:
Rabin-Karp, Knuth-Morris-Pratt, Aho-Corasick

**
Linear Programming**:
geometric intuition of Simplex Algorithm

Algovision is used for teaching algorithm at the Charles University (advanced
undergraduate course), a textbook based on Algovision (Czech and English
edition) is expected in the second quarter of 2006. The applets are designed to
show not only how, but also *why* the algorithms work, in certain cases
even proof of correctness and/or complexity is visualized or animated.

*presented at European Symposium on Algorithms 2005.