Homework Assignment 1, due Wed, Feb 24
Tom Hayes
Here is your first homework assignment. Please write up your answers
neatly, or,
better still, type them up using something like Latex or Lyx. You can
turn in your
answers in class on the due date, Wed, Feb 24 (3 weeks from today), or
you can
email me your PDF file (by midnight of the same day), and save part of
a tree.
Here are the first two problems. I will send the rest in a follow-up
email later today.
1. Impoving Karger's algorithm.
(a) Decide how best to implement Karger's min-cut algorithm
using some sort mutable data structure to store the contracted
graphs as you go. What is the worst-case cost for doing the i'th
edge contraction, up to a constant factor (use big-O notation)?
Your answer should be a function of n and i only.
(b) Sum this over i, and multiply by n^2 to get an estimate for the
expected running time of Karger's min-cut algorithm as given.
(c) See Exercise 1.25(b) in the textbook for inspiration.
For each 1 <= i <= n, compute the probability that a particular
min-cut survives the first i steps of Karger's algorithm (i.e.,
has none of its edges contracted). Note that this function
decreases with i. This suggests that the first steps of Karger's
algorithm are more reliable than the last steps, and so perhaps
do not need to be redone as often. Use this idea to improve
Karger's algorithm as much as you can. Analyze:
(i) the failure probability.
(ii) the expected number of times an i'th edge will be chosen for
contraction in your algorithm.
(iii) the expected overall running time of your algorithm.
2. (a) Prove that, if A_1, A_2, ..., A_n are n independent events,
each of probability 1/2, defined over a probability space Omega,
then Omega has cardinality at least 2^n.
(b) See exercise 1.21 for warm-up.
We say events B_1, B_2, ..., B_n are PAIRWISE INDEPENDENT
if any two of them, say, B_i and B_j are independent, where
i, j are unequal. Construct, for any n, a probability space
Omega of size O(n^2) and pairwise independent events B_1, ..., B_n
defined on Omega, each having probability 1/2.
Tom Hayes
Here is the rest of Assignment 1. 8 problems in all.
The numbered Exercises are from Mitzenmacher & Upfal.
I'll revise the due date to Friday, Feb. 26, so that you have
a full 3 weeks.
-- Tom
3. Let Omega be uniform probability space whose elementary
events are the graphs on n vertices. Define the random variable
f: Omega --> Reals as the number of triangles in the graph.
(a) Recall the expectation of f (computed in class).
(b) Calculate the variance of f. Hint: indicator variables.
Hint 2: some pairs of indicator variables will be independent,
and some will not.
(c) Apply Chebyshev's inequality to bound the probability
that a random graph has more than (3/16)(n choose 3) or
fewer than (1/16)(n choose 3) triangles. For what values of
n is this bound on the probability < 1/1000?
4. Exercise 1.6
5. Exercise 1.10
6. Exercise 1.22(b)
7. Exercise 2.18
8. Exercise 2.20
Also recommended for practice (but not to turn in):
Exercises 1.15 (try not to read the hint!) 1.18, 2.1, 2.3, 2.4, 2.8,
2.9, 2.10, 2.16, 2.17, 2.18, 2.19, 2.20, 2.26, 2.27, 2.31