Against all Odds: The amazing but most true story of Aviezri Fraenkel and his special favorite: The responsa project or the multi-faceted contributions of Aviezri Fraenkel to information retrieval and the related areas.
This paper presents a method for obtaining the expected number of data movements executed by the well-known Selection sort algorithm along with its corresponding variance. The approach presented here requires hardly any specific mathematical background. In particular, the average-case cost and variance are represented using recurrence relations whose solutions lead to the desired results. Even though this method is not applicable in general, it serves to conveniently present average-case algorithm...
We analyse three algorithms: exponentiation by squaring, calculation of maximum, and sorting by exchanging in terms of program algebra over an algebra.
The paper discusses the application of a similarity metric based on compression to the measurement of the distance among Bulgarian dia- lects. The similarity metric is de ned on the basis of the notion of Kolmo- gorov complexity of a le (or binary string). The application of Kolmogorov complexity in practice is not possible because its calculation over a le is an undecidable problem. Thus, the actual similarity metric is based on a real life compressor which only approximates the Kolmogorov complexity....