Research Article
Randomized Algorithms: Methods and Techniques
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 28 - Issue 11 |
| Published: August 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 },
year = { 2011 },
volume = { 28 },
number = { 11 },
pages = { 29-32 },
doi = { 10.5120/3436-4510 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2011
%A Kuldeep Sharma
%A Dr. Deepak Garg
%T Randomized Algorithms: Methods and Techniques%T
%J International Journal of Computer Applications
%V 28
%N 11
%P 29-32
%R 10.5120/3436-4510
%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
- 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
- Rajeev Motwani and Prabhakar Raghavan: 1996 Randomized Algorithms in ACM Computing Surveys Vol.28, No.1 Page no 33-37.
- Hoare, C. A. R.1961 Partition: Algorithm 63, Quicksort: Algorithm 64, and Find: Algorithm 65. Comm. ACM 4(7), 321-322,
- 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.
- Karp R.M., Rabin M.O., 1987, Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2):249-260.
- Carter, Larry; Wegman, Mark N. 1979. Universal Classes of Hash Functions. Journal of Computer and System Sciences 18 (2): 143–154.
- 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.
- 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.
- R.W and Rivest 1975. Expected time bounds for selection. Commun. ACM 18, 165–172.
- Snir,M. 1985. Lower bounds on probabilistic linear decision trees. Theory of Computer Science. 38, 69–82.
- Sinclair, A. 1992. Algorithms for Random Generation and Counting: A Markov Chain Approach. Progress in Theoretical Computer Science. Birkhauser, Boston.
- Wai Ki Ching, Michael K. Ng- 2006 Markov Chains: Models, algorithm and applications ISBN-10:0-387-29335-3
- Karp, R.M :1991 AN introduction to randomized algorithm, Discrete Applied Mathematics 165-201.
- Jaroslaw Byrka, Aravind Srinivasan, Chaitanya Swamy: 2010 Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm CoRR abs/ 1003.1295
- Floyd, R.W and Rivest, R.L:1975. Expected time bounds for selection. Commun. ACM 18, 165–172.
Index Terms
Keywords