CFP last date
20 June 2024
Reseach Article

Randomized Algorithms: Methods and Techniques

by Kuldeep Sharma, Dr. Deepak Garg
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 28 - Number 11
Year of Publication: 2011
Authors: Kuldeep Sharma, Dr. Deepak Garg
10.5120/3436-4510

Kuldeep Sharma, Dr. Deepak Garg . Randomized Algorithms: Methods and Techniques. International Journal of Computer Applications. 28, 11 ( August 2011), 29-32. DOI=10.5120/3436-4510

@article{ 10.5120/3436-4510,
author = { Kuldeep Sharma, Dr. Deepak Garg },
title = { Randomized Algorithms: Methods and Techniques },
journal = { International Journal of Computer Applications },
issue_date = { August 2011 },
volume = { 28 },
number = { 11 },
month = { August },
year = { 2011 },
issn = { 0975-8887 },
pages = { 29-32 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume28/number11/3436-4510/ },
doi = { 10.5120/3436-4510 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:14:32.545984+05:30
%A Kuldeep Sharma
%A Dr. Deepak Garg
%T Randomized Algorithms: Methods and Techniques
%J International Journal of Computer Applications
%@ 0975-8887
%V 28
%N 11
%P 29-32
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Randomized Algorithms are now gaining the attention of researchers. The reason is that some of the randomized algorithms have been successfully implemented in important applications reducing the time complexity and other computing resources. This paper reviews the different methods and techniques available in randomized algorithms. Paper also gives the gaps in the existing research and the future scope of research in this area.

References
  1. Donald Knuth.1997 The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley,. ISBN 0-201-89685-0. Pages 113–122 of section 5.2.2: Sorting by Exchanging
  2. Rajeev Motwani and Prabhakar Raghavan: 1996 Randomized Algorithms in ACM Computing Surveys Vol.28, No.1 Page no 33-37.
  3. Hoare, C. A. R.1961 Partition: Algorithm 63, Quicksort: Algorithm 64, and Find: Algorithm 65. Comm. ACM 4(7), 321-322,
  4. Solovay, R. and Strassen, V. 1977. A fast Monte-Carlo test for primality. SIAM J. Comput. 6, 84–85 & SIAM J. Comput. 7, 1 (Feb.), 1978, 118.
  5. Karp R.M., Rabin M.O., 1987, Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2):249-260.
  6. Carter, Larry; Wegman, Mark N. 1979. Universal Classes of Hash Functions. Journal of Computer and System Sciences 18 (2): 143–154.
  7. Freivalds, R. 1977. Probabilistic machines can use less running time. In Information Processing 77, Proceedings of IFIP Congress 77, Gilchrist, Ed., (Aug.), North-Holland, Amsterdam, 839–842.
  8. Yao,A.C-C.1977.Probabilistic computations Towards a unified measure of complexity. In Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 222–227.
  9. R.W and Rivest 1975. Expected time bounds for selection. Commun. ACM 18, 165–172.
  10. Snir,M. 1985. Lower bounds on probabilistic linear decision trees. Theory of Computer Science. 38, 69–82.
  11. Sinclair, A. 1992. Algorithms for Random Generation and Counting: A Markov Chain Approach. Progress in Theoretical Computer Science. Birkhauser, Boston.
  12. Wai Ki Ching, Michael K. Ng- 2006 Markov Chains: Models, algorithm and applications ISBN-10:0-387-29335-3
  13. Karp, R.M :1991 AN introduction to randomized algorithm, Discrete Applied Mathematics 165-201.
  14. Jaroslaw Byrka, Aravind Srinivasan, Chaitanya Swamy: 2010 Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm CoRR abs/ 1003.1295
  15. Floyd, R.W and Rivest, R.L:1975. Expected time bounds for selection. Commun. ACM 18, 165–172.
Index Terms

Computer Science
Information Sciences

Keywords

Randomized Algorithms LP Rounding Monte Carlo