Question

advantages and disadvantages of randomised algorithm over deterministic algorithm

Answer 1

Answer:

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.

The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits.

Explanation:

Randomized splay trees

Martin Fürer

Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, 903-904, 1999

The performance of the original version of the splay tree algorithm has been unchallenged for over a decade. We propose three randomized versions with better upper bounds on the expected running times (by constant factors). The improvements a. re particularly strong if the number of in-sertions is relatively small. All expectations are taken over the coin tosses of the randomized algorithms for worst case inputs. Hence slow running times are very unlikely for any reh_uest sequence. Algorith? n A improves the expected run-nine: time, but could be very slow (with tiny mobability). Alg&ithm’B shows that wiihout &y loss in ‘the origin& amortized running time, the expected running time can still be improved by a constant percentage. Algorithm C has the same efficient expected running time as Algorithm A, while its (worst case) amortized running time deteriorates only by a constant factor compared to standard deterministic splaying.