Hint for Problem 4

Here's a handy hint for problem 4 on the most recent problem set:

Suppose L_t and R_t are the partition your algorithm has selected at time t. Define some integer valued potential function f(L_t, R_t) such that f is always in some bounded range [o, R].

Show that:

1) If we ever have f(L_t, R_t) = R, then L_t, R_t is a triangle free partition

2) Pr[f(L_t+1,R_t+1) = f(L_t, R_t) + 1 ] = Pr[f(L_t+1,R_t+1) = f(L_t, R_t) - 1 ]

Then all you have to do is analyze the evolution of the potential function: and this is just a random walk on a line graph of length R.

Corrections to Homework 5

Hi,

Here are two corrections to homework 5 question 2, sorry for overlooking these.

part 2 (thanks to Julian for pointing this out): the algorithm given needs to first pick a random middle element before partitioning to guarantee random sequences. The algorithm has been modified.

fact (thanks to Henry for pointing this out): the right side of the bound ($S \leq (1 -1/e ) n + \epsilon n$ ) is erroneous and has been removed.

Richard,