Homework Assignment #4 Solution

Question 1. (1 marks)

Given an array A[1::n] of integers and an integer x to search for, consider the following \lucky search" algorithm, where r is an arbitrary integer such that r 1:

I := f1; 2; : : : ; ng // set of indices

repeat r times

pick i uniformly at random from I

if x = A[i] then return True // x was found

end repeat

return False // x was not found

Note that there are circumstances under which this algorithm may return False even if x is in A[1::n].

In the following, suppose there are exactly k copies of integer x in A[1::n].

What is the probability that this algorithm returns True in the rst iteration of the repeat loop? Justify your answer.

What is the probability that this algorithm returns True? Justify your answer.

We now modify the algorithm as follows:

I := f1; 2; : : : ; ng // set of indices

repeat forever

pick i uniformly at random from I

if x = A[i] then return True // x was found

end repeat

What is the expected number of loop iterations of this algorithm? Justify your answer.

Question 2. (1 marks)

You are given a list of m constraints over n distinct variables x1; x2; :::; xn. Each constraint is of one of the following two types.


1. An equality constraint of the form xi = xj for some i; j where 1 i 6= j n.


2. An inequality constraint of the form xi 6= xj for some i; j where 1 i 6= j n.


For such a list of constraints, it may be possible to assign an integer to each variable such that this assignment does not violate any of the constraints in this list, or such assignment may not exist.


For example, the assignment of (1; 2; 1; 1; 2) to the variables x1; x2; x3; x4; x5, satis es all the constraints in the list:

x1 = x4; x1 = x3; x1 6= x2; x2 6= x3; x2 = x5


However, no possible assignment of integers to the variables x1; x2; x3; x4; x5; x6; x7, can satisfy all the constraints in the list:


x5 = x1; x1 = x6; x4 = x5; x1 = x3; x2 6= x6; x2 = x7; x3 6= x4


Design an e cient algorithm, which takes as input a list of m constraints over n variables, and outputs an assignment of integers to variables that satis es all the constraints in this list, and if no such assignment exists the algorithm outputs nil. Describe your algorithm in clear and concise English and analyze its worst-case time complexity. The worst-case running time of your algorithm must be asymptoti-cally better than O(mn).


Hint: Use a data structure that we learned in class.

[The questions below will not be corrected/graded. They are given here as interesting problems that use material that you learned in class.]



Question 3. (0 marks) Consider the sorting algorithm given by the pseudocode below. It takes an array A[1 : : n] of size n, and outputs A with its elements in sorted (non-decreasing) order.


for i = 2 to n

2 j = i 1

while A[j + 1]   A[j] & j 1

swap A[j] and A[j + 1]

5 j = j 1

In the following subquestions, assume that the array A contains a uniformly chosen random permutations of the integers 1; : : : ; n.

Let Si be the number of swaps performed by the algorithm in the i-th iteration of the for-loop. What is the exact expected value of Si as a function of n and i? Justify your answer.

Let S = S1 + : : : + Sn 1 be the total number of swaps performed by the algorithm. What is exact expected value of S as a function of n? Justify your answer.

Question 4. (0 marks) Assume you have a biased coin, which, when ipped, falls on Heads with probabil-ity p, where 0   p   1, and on Tails with probability 1 p. However, you do not know p. How can you use the coin to simulate an unbiased coin? Formally, you have access to a procedure FlipBiasedCoin(), which returns either 1 or 0 at random. FlipBiasedCoin() returns 1 with probability p, and 0 with probability

p, but you do not know p. Design an algorithm that, without making any other random choices except calling FlipBiasedCoin(), returns 1 with probability 1=2 and 0 with probability 1=2. Your algorithm should not use p. You can assume that each time you call FlipBiasedCoin(), the value it returns is independent of all other calls to it.

Describe the algorithm in clear and concise English, and prove that it outputs 0 with probability 1=2 and 1 with probability 1=2.

Analyze the expected running time of your algorithm. Note that while the algorithm itself does not use p, the expected running time should be expressed in terms of p.

Question 5. (0 marks) Consider the following \Graph Dismantling Problem". Let G = (V; E) be a
connected undirected graph with n 4 nodes V = f1; 2; : : : ; ng and m edges. Let e1; e2; : : : ; em be all the edges of G listed in some speci c order. Suppose that we remove the edges from G one at a time, in this order. Initially the graph is connected, and at the end of this process the graph is disconnected. Therefore, there is an edge ei, 1 i m, such that just before removing ei the graph has at least one connected component with more than bn=4c nodes, but after removing ei every connected component of the graph has at most bn=4c nodes. Give an e cient algorithm that determines this edge ei. Assume that is given to the algorithm as a (plain) linked list of the edges appearing in the order e1; e2; : : : ; em. The worst-case running time of your algorithm must be asymptotically better than O(mn).


Hint: See \An application of disjoint-set data structures" in pages 562-564 of CLRS (Chapter 21).


Question 6. (0 marks) Consider the forest implementation of the disjoint-sets abstract data type, with an initial forest of n distinct elements (each one in a one-node tree). Let be any sequence of k UNIONs followed by k0 FINDs; so all UNIONs occur before the FINDs. Prove that the algorithm using Path Compression only (it does not use the Weighted-Union rule) executes in O(k + k0) time, i.e., in time proportional to the length of , in the worst-case.


Do not make assumptions on k or k0 (for example, do not assume that k = n 1 or that k0 k). As we did in class, assume that the parameters of each UNION are two set representatives, i.e., two tree roots (so there are no FINDs \inside" each UNION).

Hint: Note that if a vertex becomes a child of a root during the execution of one of the FINDs (because of Path Compression), then it remains a child of this root during all the subsequent FINDs. Use this to compute the \cost" of executing all the k0 FINDs.