Scribd
Upload
6 views1 page

Quick Select and Finding Value of Function

The document describes the randomized algorithm Rand-QSelect for finding the k-th smallest element in a set of real numbers, detailing its process and expected performance. It also presents a problem involving a function F affected by an adversary, proposing a randomized algorithm to estimate F(z) despite changes in the lookup table. Additionally, it discusses the probability of correctness when the algorithm is repeated multiple times.

Uploaded by

luaaannd
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views1 page

Quick Select and Finding Value of Function

The document describes the randomized algorithm Rand-QSelect for finding the k-th smallest element in a set of real numbers, detailing its process and expected performance. It also presents a problem involving a function F affected by an adversary, proposing a randomized algorithm to estimate F(z) despite changes in the lookup table. Additionally, it discusses the probability of correctness when the algorithm is repeated multiple times.

Uploaded by

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

CS648A : Randomized Algorithms

Department of Computer Science and Engineering, IIT Kanpur

1 Randomized quick select


Let S be a set of n real numbers. Consider the randomized algorithm Rand-QSelect(k, S) described below
that finds the k th smallest element from the set S.

Select a pivot element x uniformly randomly from set S.


Find its rank in the set S (by comparing x with every other element of set S). Let r be the rank of x.
If r = k, we report x as the output. Otherwise we proceed recursively as follows:
If r > k, then Rand-QSelect(k, S<x )
Else Rand-QSelect(k − r, S>x ).

Where S<x and S>x are the sets consisting of all those elements that are respectively smaller and greater
than the element x. Observe that the running time of the above algorithm is dominated by the number of
comparisons performed. Therefore, in order to get a bound on the expected running time of the algorithm,
our aim is essentially to find out the expected number of comparisons performed in Rand-QSelect(k, S).
Prove the following statements.

1. The expected number of comparisons is at most 3.5n.

2. There are elements in set S which will be compared expected Θ(log n) times during the algorithm.

2 Making an intelligent guess


We have a function F : {O, ..., n − 1} → {O, ..., m − 1}. We know that, for 0 ≤ x, y ≤ n − 1,

F ((x + y) mod n) = (F (x) + F (y)) mod m

The only way we have for evaluating F is to use a lookup table that stores the values of F . Unfor-
tunately, an Evil Adversary has changed the value of 1/5 of the table entries when we were not looking.
Describe a simple randomized algorithm that given an input z, outputs a value that equals F (z) with
probability at least 1/2. Your algorithm should work for every value of z, regardless of what values the
Adversary changed. Your algorithm should use as few lookups and as little computation as possible.
Suppose I allow you to repeat your initial algorithm k times. What should you do in this case, and
what is the probability that your enhanced algorithm returns the correct answer?

You might also like