We will grade a subset of the assigned questions, to be determined after the deadline, so that we can provide better feedback on the graded questions.

For bonus questions, we will not provide any insight during office hours or Piazza, and we do not guarantee anything about the difficulty of these questions.

We strongly encourage you to typeset your solutions in LATEX.

If you collaborated with someone, you must state their name(s). You must write your own solution

for all problems and may not look at any other student’s write-up.

0. If applicable, state the name(s) and uniqname(s) of your collaborator(s).

1. This question is a crash course (hopefully, review) on discrete probability. The basic premise is that we would like to model a random experiment with a countable set of outcomes Ω, each outcome ω ∈ Ω occurring with some probability p(ω) ∈ [0, 1]; the sum of the prob-

abilities, Σ ω∈Ω p(ω), is 1. An event A is a subset of Ω and it occurs with probability

conduct an experiment; formally, it is a function X : Ω → R. If we run an experiment and record the value a for X, we denote this event as {X = a}.  We  denote the probability of  this event as Pr[X = a].  There are other events we can consider, such as {X ≤ a}, {X ≥ a},

{X < a} = {X ≥ a}, {X > a} = {X ≤ a}, {X ̸= a}, {X² > a}, and so forth. The expected value of a random variable X is E(X) := ω∈Ω X(ω)p(ω) = a∈X(Ω) a Pr[X = a].

These might seem like an overly formal, pedantic definitions, but probability is quite subtle and, often times, the difficulty in questions is wrapping your mind around the underlying experiment that is being conducted.

(a) Show that for any random variable X and real number a, Pr[X ≥ a] = 1 − Pr[X < a]. Similarly, show that Pr[X ≤ a] = 1 − Pr[X > a].   

Hint : Show that Pr[A] + P[A] = 1, where event A = Ω \ A is the complement of event

A. You can show that Pr[A] + Pr[A] = 1 by finding a way to rewrite Pr[A] and Pr[A]

(b) Show that for any random variable X, there is some outcome ω ∈ Ω such that X(ω) ≥

E[X]. In class, we called this an averaging argument.

Hint : Try a proof by contradiction and look at the definition of E(X).

(c) Suppose you flip a biased coin, with probability 0 < p < 1 of heads (and 1 − p of tails), n times. Model the experiment using discrete probability (in particular, say what Ω and p(ω) are). Let X be the number of heads that you see. Compute E[X].

Hint : Define n indicator variables and use linearity of expectation.

(d) Same set up as in 1c but you flip the coin until you get heads. Model the experiment using discrete probability. Let X be the number of flips that you perform. Compute E[X].

Hint :  ShowΣthat E[X] = Σ∞n=1 n(1 − p)ⁿ⁻¹p.  Then factor the p out and rewrite E[X] as

2. Here is a randomized algorithm for producing a cut in a graph tt = (V, E):

1. Initialize S to be the empty set.

2. For each vertex v in V:

Put v into S with probability 1/2.

3. Output (S, T = V \ S).

For an undirected graph, E(S, T ) is the set of edges “crossing” the cut (S, T ), i.e., those that have one endpoint in S and the other endpoint in T . The size of the cut is |E(S, T )|.

(a) Prove that the above algorithm is a ¹ -approximation in expectation for MaxCut on undirected graphs. That is, the expected size of the output cut is at least half the size of a maximum cut.

Hint: use linearity of expectation to show that in expectation, half the edges of the graph are in E(S, T ).

(b) Argue that, for any undirected graph tt = (V, E), there exists a cut of size at least ^|E| .

3. The randomized algorithm Randomized-Quicksort (which is Quicksort with pivots chosen at random) has worst-case running time Θ(n²), but expected running time O(n log n) when run on any array of n elements. In practice, well-implemented Quicksort is faster than all the other O(n log n)-time sorting algorithms on “generic” data.

Prove that for any array A of n elements, and any constant c > 0,

lim

n→∞

Pr[Randomized-Quicksort on input A takes at least cn² comparisons] = 0.

That is, Randomized-Quicksort is very unlikely use Ω(n²) comparisons.

Hint: The number of comparisons Randomized-Quicksort uses is a random variable. You do not need to know anything about how Quicksort or Randomized-Quicksort work; just use the above facts and Markov’s inequality.

4. In the maximum independent set problem, given a graph tt, the goal is to find a largest independent set in tt. Suppose that every vertex in tt has at most ∆ neighbors. The following is a randomized ¹ -approximation algorithm for the problem in this case.

(a) Show that S is an independent set.

(b) Show that, for a given vertex v, the probability of the vertex being the first among its neighbors in the ordering specified in line 3 of the algorithm is at least ¹ .

(c) Show that the expected size of S is at least ^|V | . Hint : Make indicator random variables

X_v for each vertex v and use linearity of expectation.

(d) Explain why tt must have an independent set of size at least ^|V |

and also explain why

the algorithm is an ¹ -approximation, in expectation. Hint : See 1b.

5. One concern when running randomized algorithms with outputs which may vary in quality is how do we  know we  have  a “good” output - the guarantees of the algorithm may hold  in expectation, but that does not mean that the outputs of the algorithm are actually good quality. It turns out that running the algorithm many times (independently) can be sufficient to deal with this concern.

For example, we have an approximation algorithm for the maximum cut problem which yields a  ¹ -approximation in expectation.  Any  cut which we  generate is not necessarily a  1 -approximation to the optimal solution, but running the algorithm “infinitely many times” will give a ¹ -approximation.

Assume that |E| > 0.

(a) Show that the probability of not getting a ¹ -approximation on any one run of the maximum cut algorithm is strictly less than 1.

Hint : Consider the number of edges which are not cut and use Markov’s inequality.

(b) Let c denote the probability of not getting a ¹ -approximation on any one run of the

maximum cut algorithm.

Suppose you run the maximum cut algorithm (on a given graph) 8 times, independently. Compute the probability that none of the 8 outputs are a ¹ -approximation.

(c) Describe a way to aggregate the results of T independent runs of the maximum cut algorithm in such a way that the probability of not getting a ¹ -approximation after T independent runs of the algorithm can be made to be c^T (for c as defined above).

6. Bonus. Here’s an interesting problem that might have implications for real life¹. Suppose you have time to date at most n people in your quest to find the best possible partner. Since human beings are quite complex, you can only compare any two people and say which one is the better of the two. Hence, you can only know who the best one is after you’ve dated all of them. Assume that you can only date one person at a time² and after you date someone, you have to commit to either partnering up with them (and stopping your search) or rejecting them (and continuing your search).

A natural strategy is: (i) reject the first m ≥ 1 people you date (to “play the field” a little) and then (ii) partner up with the first person that’s better than all of the previous people

you’ve dated. Assuming that you encounter and date the n people in random order, it turns out that choosing m = n/e ≈ n/2.718 gives you the best odds of partnering up with the best

one, which works out to be 1/e ≈ 0.367.

(a) Let E_i be the event that the i-th person is the best one and that you partner up with them.  Compute Pr[E_i] with proof.

Hint : If you are having trouble, try using part (b) to “reverse engineer” this probability.

(b) Let E be the event that you partner up with the best one. Show that

n

m  1 

Pr[E] = .