[SOLVED] Cs240 algorithm design and analysis problem set 5

Problem 1:
Suppose you have 2n balls and 2 bins. For each ball, you throw it randomly
into one of the bins. Let X1 and X2 denote the number of balls in the two bins
after this process. Prove that for any ε > 0, there is a constant c > 0 such that
the probability Pr [X1 − X2 > c√
n] ≤ ε.Problem 2:
Suppose that for a certain decision problem, we have an algorithm which computes the correct answer with a probability at least 2/3 on any instance. We
wish to reduce the error probability by running the algorithm n times on the
same input, using independent randomness between trials, and taking the most
common result as the final answer. Using Chernoff bounds, provide an upper
bound on the probability that this modified algorithm produces an incorrect
result.Problem 3:
Suppose you have n coins, where the i’th coin has a size ci > 0, and many piggy
banks, each with a uniform capacity V , such that V ≥ max(ci). You want to
place all the coins into the minimum number of piggy banks. To do this you
use the following greedy strategy. Start with one active piggy bank. Then,
sequentially go through the coins, attempting to place each coin into any active
piggy bank where it fits. If a coin does not fit into any active piggy bank, take
a new piggy bank and make it active. The algorithm is shown below. Prove
this algorithm is a 2-approximation, i.e. it uses at most two times the minimum
number of piggy banks needed for all the coins.Algorithm 1 Piggy Bank Coin Packing
1: Input: Sizes of coins c1, c2, . . . , cn; size of piggy bank V
2: Output: Number of piggy banks used
3: Initialize b ← 1 ▷ current number of active piggy banks
4: Initialize P1, P2, . . . ← 0 ▷ space used in each piggy bank
5: for i = 1 to n do
6: if ∃j ≤ b such that Pj + ci ≤ V then
7: Choose any j with Pj + ci ≤ V
8: Pj ← Pj + ci ▷ put ci
in j-th active piggy bank
9: else
10: b ← b + 1
11: Pb ← ci ▷ open a new piggy bank and put ci
in it
12: end if
13: end forProblem 4:
Consider an n × n grid graph G, as shown below.
Each node v in G has a weight w(v) > 0. You want to choose an independent
set of nodes with maximum total weight. That is, you want to choose a set of
nodes S with maximum total weight such that for any v ∈ S, none of v’s
neighbors are in S.To do this, consider the following greedy algorithm. Let
V be the set of all nodes in G. Choose the node in V with the largest weight
(breaking ties arbitrarily), add it to the independent set, then remove the node
and all its neighbors from V . Repeat this process until V is empty. Let S be
the output of this algorithm. Solve the following problems.1. Let T be any independent set in G. Show that for each node v ∈ T, either
v ∈ S, or there is a neighbor v
′ of v with v
′ ∈ S and w(v) ≤ w(v
′
).
2. Show that the greedy algorithm is a 4-approximation.