What are randomized algorithms and their analysis techniques?

Randomized algorithms use random choices during execution. Las Vegas algorithms always give correct result with random runtime (e.g., randomized quicksort - expected O(n log n)). Monte Carlo algorithms may give incorrect result with bounded probability (e.g., primality testing). Analysis uses expected value and probability bounds. Benefits: simpler, avoid worst cases, resist adversarial inputs. Examples: randomized selection, skip lists, Bloom filters, Min-Cut algorithm.