A Survey on Randomized Algorithms and its Applications

Volume: 4    Issue: 3

Year of Publication: 2017

Pages: (1-6)

Authors: Jaimeen K Patel, Sanjay S,Girish Rao Salanke N S

Download Full Text (PDF)

Abstract

Randomization has become a standard approach in algorithm design due to its efficiency and simplicity. It has been used in wide spread applications, especially in the areas of communication, cryptography, data management, and discrete optimization. This paper is aimed towards exploring the paradigms of Randomized algorithms. The paper also gives some applications of randomized algorithm in different areas and concludes giving future application areas.

References

1. Karpinski, M., and Verbeek, R., On Randomized versus Deterministic Computation, Proc. ICALP \"93, LNCS 700 (1993), Springer-Verlag, pp. 227–240.

2. Hromkovich, \"Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms\", Springer, Berlin–Heidelberg (2005).

3. J. Hromkovic , I. Z´amecnikov,” Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms”, Texts in Theoretical Computer Science, an EATCS series. Springer, first edition, July 2005. ISBN: 978-3-54023-949-9.

4. R. Motwani and P. Raghavan, ” Randomized Algorithms”, Cambridge University Press, 1995.

5. Sariel Har-Peled,“Lectures notes on Randomized Algorithms” ,2005.

6. D. Randall. Rapidly mixing markov chains with applicationsin computer science and physics. Computing in Science and Engineering, 8(2):30–41, 2006.

7. E. Bingham, H. Mannila, \"Random Projection in Dimensionality Reduction: Applications to Image and Text Data\", Proc. ACM SIGKDD Int\"l Conf. Knowledge Discovery and Data Mining, pp. 245-250, 2001.

8. Michael T. Goodrich and Roberto Tamassia ,“Using randomization in the teaching of data structures and algorithms”, The proceedings of the thirteenth SIGCSE technical symposium on Computer science education, Pages 53-57 ,1998

9. Mihir Bellare, \"Notes on Randomized Algorithms”, Computer Science and Engineering, UCSD

10. E. Bingham, H. Mannila, \"Random Projection in Dimensionality Reduction: Applications to Image and Text Data\", Proc. ACM SIGKDD Int\"l Conf. Knowledge Discovery and Data Mining, pp. 245-250, 2001.

11. Fuchsbauer, G.J, \"An Introduction to Probabilistic Encryption\", Osjecki Matematicki List, 2006. 6 p. 37-44.

12. Romanas Tumasonis and Gintautas Dzemyda. Analysis of the statistical characteristics in mining of frequent sequences. In Intelligent Information Systems, pages 377–386, 2005.

13. Rajiv Gupta, Scott A. Smolka, Shaji Bhaskar, \"On Randomization in Sequential and Distributed Algorithms”,Journal ACM Computing Surveys (CSUR) ,Volume 26 Issue 1, March 1994 ,Pages 7-86 .

14. Hurd J, ”Formal Verification of Probabilistic Algorithms”, PhD thesis, University of Cambridge (2002).

Keywords

Algorithm, randomized, deterministic.