Scribd
Upload
38 views

Tutorial 5, Design and Analysis of Algorithms, 2024

Tutorial 5, Design and Analysis of Algorithms, 2024

Uploaded by

abhishek.mishra
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
38 views

Tutorial 5, Design and Analysis of Algorithms, 2024

Tutorial 5, Design and Analysis of Algorithms, 2024

Uploaded by

abhishek.mishra
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/ 2

Tutorial 5, Design and Analysis of Algorithms, 2024

1. (a) Consider the set { 1, 2, . . . n − 1, n }. We generate a subset X of this set as follows: a fair
coin is flipped independently for each element of the set: if the coin lands heads then the
element is added to X, and otherwise it is not. Prove that the resulting set X is equally
likely to be anyone of the 2n possible subsets.
(b) Suppose that two sets X and Y are chosen independently and uniformly at random
from all the 2n subsets of { 1, 2, . . . n − 1, n }. Determine Pr(X ⊆ Y ) and Pr(X ∪ Y =
{ 1, 2, . . . n − 1, n }).
2. Let a1 , a2 , . . . , an be a random permutation of { 1, 2, . . . , n }, equally likely to be any of the
n! possible permutations. When sorting the list a1 , a2 , . . . , an , the element ai must move a
distance of |ai − i| places from its current position to reach its position in the sorted order.
Find " #
n
E ∑ |ai − i| ,
i=1
the expected total distance that elements will have to be moved.
3. We have a function f : { 0, . . . , n − 1 } → { 0, . . . , 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 . Unfortunately, an Evil Adversary has
1
changed the value of of the table entries when we were not looking. Describe a simple
5
randomized algorithm that, given an input z, outputs a value that equals f (z) with probability
1
at least . Your algorithm should work for every value of z, regardless of what values the
2
Adversary changed. Your algorithm should use as few lookups and as little computation as
possible.
4. Prove that a coin with Pr[Heads] = ρ can be simulated by a PTM in expected time O(1)
provided the i’th bit of ρ is computable in time polynomial in i.
1
5. Prove that a coin with Pr[Heads] = can be simulated by a PTM with access to a stream of
2  
1
ρ−biased coins (Pr[Heads] = ρ) in expected time O .
ρ(1 − ρ)
6. Prove that a language L is in ZPP if and only if there exists a polynomial-time Probabilis-
tic Turing Machine M with outputs in { 0, 1, ? } such that ∀x ∈ { 0, 1 }∗ , with probability 1,
M(x) ∈ { L(x), ? } and Pr[M(x) =?] ≤ 12 .
7. Prove that the following is an alternative definition of BPP:
A Language L is in BPP if there exists a polynomial-time DTM M and a polynomial p : N →
2
N such that for every x ∈ { 0, 1 }∗ , Prr∈R { 0,1 } p(|x|) [M(x, r) = L(x)] ≥ .
3
Notation: ∈R means randomly chosen. L(x) = 1 if x ∈ L and L(x) = 0 if x ∈ / L.

1
8. Let L ∈ { 0, 1 }∗ be such that there exists a polynomial-time PTM M satisfying for every
x ∈ { 0, 1 }∗ :
(1) If x ∈ L, then Pr[M(x) = 1] ≥ n−c and
(2) If x ∈/ L, then Pr[M(x) = 1] = 0.
Prove that for every d > 0 there exists a polynomial-time PTM M ′ such that for every x ∈
{ 0, 1 }∗ :
d
(1) If x ∈ L, then Pr[M ′ (x) = 1] ≥ 1 − 2−n and
(2) If x ∈/ L, then Pr[M ′ (x) = 1] = 0.

9. A probabilistic expected polynomial-time algorithm A accepts a language L and ∃(n0 , c) ∈ N2


such that ∀|x| > n0 ,
1
x ∈ L =⇒ P[A(x) = 1] ≥ c ,
|x|
and
x∈
/ L =⇒ P[A(x) = 1] = 0.

Prove or disprove:
L ∈ RP .

10. A probabilistic expected polynomial-time algorithm A accepts a language L and ∃(n0 , c, α) ∈


N2 × [0, 1) such that ∀|x| > n0 ,

1
x ∈ L =⇒ P[A(x) = 1] ≥ α + ,
|x|c

and
x∈
/ L =⇒ P[A(x) = 1] ≤ α.
Prove or disprove:
L ∈ BPP .

You might also like