CMPSC 497: Advanced Algorithms Due 03/03/2023 at 10:00 pm
Problem Set 2
Notice: Type your answers using LaTeX and make sure to upload the answer file on Gradescope before the deadline.
For more details and instructions, read the syllabus.
Problem 1. Stocks
A simple model for the stock market works as follows: a stock with price q will increase by a factor r > 1 to qr with
probability p and will fall to q/r with probability 1? p. If we start with a stock with price 1, find formulae for the
expected value and variance of the price of the stock after T days.
Problem 2. Tight concentration
(a) Given a positive integer k, describe a random variable X assuming only non-negative values such that Markov’s
inequality is tight. That is, such that Pr[X ≥ a] = E[X ]/a.
(b) Given a positive integer k, describe a random variable X such that Chebyshev’s inequality is tight. That is, such
that Pr[|E?E[X ]| ≥ k√Var(X)] = 1/k2.
Problem 3. Another Chernoff bound.
Let X1, . . . ,Xn be n independent random variables such that Xi ∈ [ai,bi] for every i= 1, . . . ,n. Let Sn = ∑ni=iXi and let
μ = E[Sn]. Show that for any δ > 0
Pr[|Sn?μ| ≥ δ ]≤ 2exp
(
? 2δ
2
∑ni=1(bi?ai)2
)
.
Hint: Follow the prove approach from class for 0/1 random variables. When it is time to use the information about the
Xi’s, use of the fact that if Y is a random variable such that E[Y ] = 0 andY ∈ [a,b], then for any t ≥ 0, E[etY ]≤ e
t2(b?a)2
8 .
Problem 4. Balance partitioning
Given an n×n matrix A whose entries are either 0 or 1, we want to find a column vector b ∈ {?1,1}n that minimizes
∥Ab∥∞. (Recall that if Ab = c with c = (c1, . . . ,cn), then ∥Ab∥∞ = maxi=1,...,n |ci|.) Consider the following algorithm
for choosing b: each entry of b is ?1 with probability 1/2 and 1 otherwise. Show that for this choice of b, ∥Ab∥∞ =
O(
√
n lnn) with probability 1?O(n?1).
1
Problem 5. A random geometric network
Suppose n points are placed uniformly at random in the unit square. Each point is then connected to the k closest
points. Let G be the resulting random graph. Show that there exists a constant c > 0 (independent of n and k), such
that when k ≥ c logn, Pr[G is connected]→ 1 as n→ ∞.
Hint: Partition the unit square into small squares of area lognn . Show that in every small square there is at least one
point with high probability. Then, use a Chernoff bound to show that with high probability the number of points in
disc of radius
√
a logn
n is at most b logn for suitable constants a,b > 0. Show that these properties imply that G is
connected.
Problem 6. Reduction I
Given two sets, P and Q, of n points in Rn space, your task is to find x ∈ P and y ∈ Q such that ∥x? y∥2 is minimum.
(a) Show how to do this in O(n3) time.
(b) Show how to do this in time O(n2 logn) if it suffices to find to find x ∈ P and y ∈Q whose distance 1.001 times the
minimum possible distance. (If the min distance is 0, you must find x= y.)
Problem 7. Reduction II
Given n data points in Rd , where d = n5, we want to find a subset of 4 data points whose sum vector has the smallest
length. Formally, find the 4 points x1,x2,x3,x4 ∈ Rd such that ∥x1+ x2+ x3+ x4∥2 is minimized.
(a) Show how to do this in O(n9) time.
(b) Show how to do this in time O(n5 logn) if it suffices to find a subset whose sum has a length that is 1.001 the length
of the smallest possible sum.