LIPIcs.FUN.2018.23.pdf
- Filesize: 0.71 MB
- 23 pages
Document
Selection Via the Bogo-Method - More on the Analysis of Perversely Awful Randomized Algorithms
Authors
-
Part of:
Volume:
9th International Conference on Fun with Algorithms (FUN 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-04
Cite As Get BibTex
Markus Holzer and Jan-Tobias Maurer. Selection Via the Bogo-Method - More on the Analysis of Perversely Awful Randomized Algorithms. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FUN.2018.23
Abstract
We continue our research on perversely awful randomized algorithms, which started nearly a decade ago. Based on the bogo-method we design a bogo-selection algorithm and variants thereof and analyse them with elementary methods. Moreover, practical experiments are performed.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Combinatorics
- Mathematics of computing → Probability and statistics
- Theory of computation → Algorithm design techniques
Keywords
- selection
- bogo-method
- combinatorial sums and series, inverse binomial coefficients
- experimental result
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
L. Comtet. Advanced Combinatorics - The Art of Finite and Infinite Expansions. Reidel Publishing, 1974.
-
H. W. Gould. Combinatorial Identities. Morgantown Printing and Binding, 1972.
- Hermann Gruber, Markus Holzer, and Oliver Ruepp. Sorting the slow way: An analysis of perversely awful randomized sorting algorithms. In Pierluigi Crescenzi, Giuseppe Prencipe, and Geppino Pucci, editors, Fun with Algorithms, 4th International Conference, FUN 2007, Castiglioncello, Italy, June 3-5, 2007, Proceedings, volume 4475 of Lecture Notes in Computer Science, pages 183-197. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-72914-3_17.
-
D. E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley, 1969.
- D. H. Lehmer. Interesting series involving the central binomial coefficient. Amer. Math. Mon., 92(7):449-457, - 1985. URL: http://dx.doi.org/10.2307/2322496.
-
E. S. Raymond. The New Hacker’s Dictionary. MIT Press, 1996.
-
A. M. Rockett. Sums of inverses of binomial coefficients. Fibonacci Quart., 19(5):433-437, 1981.
-
R. Sedgewick and P. Flajolet. An Introduction to the Analysis of Algorithms. Pearson Education, 2013.
-
R. Sprugnoli. Sum of reciprocals of the central binomial coefficients. Integers, 6:A27, 2006.
-
B. Sury, T. Wang, and F.-Z. Zhao. Identities involving reciprocals of binomial coefficients. Integer Seq., 7:04.2.8, 2004.