Description
Homework Problems
1. (30 points) Consider a directed graph constructed by the following discrete-time process.
(Ideas along these lines have been used for building models to explain statistics of the Internet
graph and growth of peer-to-peer networks.)
You start with a single node v1. At every time step t with 1 < t ≤ n, a single node vt
is
added to the graph, together with a single outgoing edge; the destination of the edge is a
node chosen uniformly at random among the existing nodes in the graph.
Let G be the graph at the end of time step n.
(a) What is the expected number of edges entering node vj in G? Give an exact expression
in terms of n and j, as well as an asymptotic expression using Θ notation.
(b) What is the expected number of nodes with no incoming edges in G?
2. (30 points) You are given three strings X, Y , Z of lengths m, n, r respectively.
Give an efficient algorithm to compute the length of the longest common subsequence of the
three strings.
A subsequence of string s1s2 . . . sn is a subset of the characters of the string taken in order, of
the form si1
, si2
, . . . , sik where 1 ≤ i1 < i2 < . . . < ik ≤ n. For example, the longest common
subsequence of ”abc”, ”bdc” and ”bacd” is ”bc” and its length is 2.
3. (30 points) You’re asked to design a good strategy for a seller in an online auction. There
are n buyers in this auction, each with a distinct bid bi > 0. The buyers appear in a random
order and the seller must decide immediately whether to accept the current buyer’s bid or
not. If he accepts, he makes a profit of bi and the auction terminates. Otherwise, the bid is
withdrawn and the seller may see the next buyer.
Design a strategy (algorithm) that guarantees that the seller accepts the highest of the n bids
with probability at least 1/4, regardless of n, which you may assume even for simplicity.
4. (35 points) You are given some data to analyze. You have organized the process of analyzing
the data so that it consists of n tasks that have to be performed sequentially by using dedicated
hardware: you will use a processor Pi to perform task i, for every i.
You can spend D dollars to perform the analysis, where D is a polynomial in n. Each processor
is relatively cheap but may fail to complete its task with some probability, independently of
the other processors. Specifically, Pi costs ci dollars and succeeds to complete its task with
probability si
, while it fails with probability 1 − si
.
(a) (3 points) What is the probability that the process of analyzing the data will be completed successfully?
(b) Note that you can improve this success probability by using pi ≥ 1 identical processors
Pi for task i instead of just one.
i. (4 points) What is the probability that task i will be completed successfully now?
ii. (4 points) What is the probability that the process of analyzing the data will be
completed successfully now?
iii. (24 points) Your goal now is clear: on input s1, . . . , sn, integers c1, . . . , cn and integer
D, you want to assign values to p1, p2, . . . , pn so that the success probability of
analyzing the data is maximized while you’re not spending more than D dollars.
Design and analyze the time and space complexity of an efficient algorithm that
computes the maximum success probability of the entire process of analyzing the
data while spending no more than D dollars.
5. (30 points) The following randomized algorithm returns the k-th smallest number from a set
S of n distinct integers, for any k.
Algorithm 1
k-th order statistic (S, k)
1: Select an item ai ∈ S uniformly at random
2: for each item aj ∈ S do
3: Put aj in S
− if aj < ai
4: Put aj in S
+ if aj > ai
5: end for
6: if |S
−| = k − 1 then // ai is the k-th smallest item
7: return ai
8: else if |S
−| ≥ k then // the k-th smallest item lies in S
−
9: k-th order statistic (S
−, k)
10: else // the k-th smallest item lies in S
+
11: k-th order statistic (S
+, k − 1 − |S
−|)
12: end if
(a) (5 points) Show how to compute the median of S using this algorithm.
(b) (25) Analyze the expected running time of k-th order statistic (S, k).
Hint: We will say that a subproblem is of type j if its input consists of at most n
3
4
j
items but more than n
3
4
j+1 items.
Upper bound the expected time of k-th order statistic on a subproblem of type j,
excluding the time spent on recursive calls. Equivalently, upper bound the expected time
until an item ai is selected such that 1/4 of the input can be thrown out (thus the input
shrinks by a factor of 3/4).
Next obtain an upper bound to the expected running time of the entire algorithm by
summing up the expected time spent on every subproblem.
RECOMMENDED exercises: do NOT return, they will not be grade
CSOR W4231.001
