KEMBAR78
Randomized | PDF
Scribd
Upload
23 views2 pages

Randomized

Randomized algorithms utilize random numbers or decisions to solve problems, allowing for potentially simpler or faster solutions compared to deterministic algorithms. They may yield different results for the same input but often maintain a high probability of accuracy. An example is a randomized approach to finding the minimum in an array, which can be more efficient than checking every element.

Uploaded by

202300327
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
23 views2 pages

Randomized

Randomized algorithms utilize random numbers or decisions to solve problems, allowing for potentially simpler or faster solutions compared to deterministic algorithms. They may yield different results for the same input but often maintain a high probability of accuracy. An example is a randomized approach to finding the minimum in an array, which can be more efficient than checking every element.

Uploaded by

202300327
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

What are Randomized Algorithms?

A Randomized Algorithm is an algorithm that uses random numbers or random decisions at


some point during its process to solve a problem. Unlike deterministic algorithms (which always
do the same thing with the same input), randomized algorithms can behave differently even with
the same input, because they make some random choices.

Why use Randomized Algorthms?

● They can be simpler or faster than deterministic ones.


● They often help solve problems that are hard to solve efficiently otherwise.
● Sometimes they give good enough solutions quickly instead of perfect ones slowly.

Key Point:

Randomized algorithms don’t always guarantee the same output for the same input, but they
often have a high probability of giving the correct or near-correct answer.

Simple Example: Randomized Algorithm to Find Minimum in an Array

Problem: Find the minimum number in an array of integers.

Deterministic Approach: Check every element and keep track of the smallest one (time
complexity: O(n)).

Randomized Approach:

1. Pick a random element from the array.


2. Check if it is the minimum by comparing it with some other random samples.
3. If it looks like the smallest, return it; else repeat or check more samples.

Simple Pseudo Code Example:


Algorithm RandomizedMin(A, n)
Input: An array A of n numbers
Output: An element that is minimum (with high probability)

1. Pick a random element x from A


2. For i = 1 to k (some small number of tries)
Pick another random element y from A
If y < x then
x = y
3. Return x

Here, by randomly sampling a few elements and updating the candidate minimum, you get a
high chance of getting the actual minimum, but the algorithm runs faster for very large arrays
compared to checking every element.

Summary Randomized algorithms use randomness to make decisions.

● They can be simpler or faster than standard algorithms.


● Results may vary on each run, but often the probability of a wrong answer is low.
● Examples include algorithms in searching, sorting, and optimization problems.

You might also like