Understand Randomized Algorithms once and for all

Randomized algorithms use a certain amount of randomness as part of their logic. And counter-intuitively, the randomness can actually help us solve certain problems better than we could have otherwise! In this post, we discuss what randomized algorithms are, and have a look at the Solovay-Strassen Primality Tester to see what they are like.

Introduction

Randomized algorithms use a source of randomness to make their decisions. They are used to reduce usage of resources such as time, space or memo...