Algorithm visualization is an educational tool that has been used for many years to show the progress of an algorithm by updating a visual representation of a data structure. Visualizations usually cover CS1 and CS2 algorithms. However, algorithm animations and high level data structure visualizations are not yet widely used in algorithm learning.

The poster presents Algovision (see www.algovision.org), both an algorithm visualization tool and a visualization philosophy presenting algorithms as they were or could have been conceived in the mind of their discoverer.

In wireless networks, simultaneously active transmitters typically operate in separate communication channels to avoid mutual interference. This study focuses on the challenge of increasing the capacity of a wireless network by enabling multiple transmissions in each available channel. Active transmitters are assumed to maintain the receiver signal-to-noise-and-interference ratio (SINR) at a predetermined target value via power control to promote the quality of wireless connections. To this end, we propose distributed medium access algorithms that allow every transmitter-receiver pair to determine whether a target SINR is physically achievable through iterative power control in a given shared channel. The proposed algorithms are shown by theoretical analysis to be fast, accurate, and energy efficient. Numerical simulations demonstrate their ability to outperform related medium access schemes based on random access, carrier sensing, controlled power up, or invariant channel probing. Our major contribution consists of solving the open problem of accurate real-time computation of the spectral radius of an unknown network information matrix. This makes our framework applicable not only to testing target SINR achievability, but also to other aspects of wireless engineering such as energy efficiency, power control stability, and handover prioritization, in which knowledge of the spectral radius plays a key role.

An important performance measure in wireless networks is the manner in which the network can distributively manage its limited energy and spectrum resources, while assuring certain quality of service for communicating users. The current practice is to develop schemes with low complexity that are based on workable, but theoretically suboptimal techniques such as random access or carrier sensing. To address the need for equally simple, but optimally performing resource management schemes, we propose a set of optimum distributed algorithms for adaptive admission control and power control, which jointly (i) maximize the number of transmitters that transmit simultaneously in shared channel(s) with a guaranteed target signal-to-interference and noise ratio (SINR) at the receiver; (ii) minimize the transmit powers required to satisfy the SINR targets; (iii) use interference measurements as the only decision-making input; and (iv) provide inadmissible links with feedback on feasible SINR for (re)admission purposes. Unlike previous studies in which SINR targets were assumed as constants, we defined these targets using arbitrary linear functions of interference. From numerical simulations, it is confirmed that the proposed scheme outperforms other schemes by achieving the theoretical performance bounds.

In order to obtain the lowest possible latency, routing algorithms should try to avoid a message waiting for resources (network links) blocked by other messages or multiplexing of more messages over one physical channel. This requirement becomes especially important in the case of long messages. The only type of protocols able to guarantee waiting free routing under heavy load are algorithms based on deflection (also called nonminimal adaptive or hot potato) routing. This paper deals with problems connected with the use of deflection algorithms. In contrast to the case of nonadaptive or partially (e.g., minimal) adaptive routing, it is very infrequent that an unrestricted deflection routing becomes deadlocked and, similarly, livelock is not a serious problem. On the other hand, there is another phenomenon, called a deflection jam, that limits throughput of deflection algorithms used to route long messages. It has been observed for many deflection heuristics, interconnection network topologies, and both virtual cut-through and wormhole routing. A deflection jam is a sudden and persistent saturation of a network which sometimes occur, after a very long period of undisturbed communication. This paper describes events that trigger this saturation which suggest ways to design improved and stable deflection routing algorithms.

No abstract available.

We show that 2-term DNF formulae are learnable in quadratic time using only a logarithmic number of positive examples if we assume that examples are drawn from a bounded distribution. We also show that k-term DNF formulae are learnable in polynomial time using positive and negative examples drawn from a bounded distribution.

Two problems are said to be polynomially equivalent if each is polynomially reducible to the other. A problem is said to be isomorphism-complete if it is polynomially equivalent to the graph isomorphism problem. We prove that the isomorphism problem in any variety of unary algebras is either isomorphism-complete, or solvable in polynomial time. We formulate a condition C under which the isomorphism problem in a variety V of unary algebras can be solved in polynomial time. We present an algorithm that can be applied to any pair of unary algebras with the same number of operations and decides whether the algebras are isomorphic or not in $O(n^3 )$ time, provided one of them belongs to a variety satisfying C. The validity of the last condition is tested by the algorithm in linear time.

An algorithm is presented to compute a canonical form of regular graphs. There is a constant c such that for each constant d the average running time of the algorithm over all d-regular graphs with N vertices is not greater than cNd, provided N is sufficiently large.

Canonical labelling of graphs (CL, for short) can be used, e.g., to test isomorphism. We prove that a simple vertex classification procedure results after only two refinement steps in a CL of random graphs with probability 1 - exp(-cn). With a slight modification we obtain a linear time CL algorithm with only exp(-cn log n/log log n) probability of failure. An additional depth-first search yields a CL of all graphs in linear average time.