Changes to Homework 6 Scoring

Hi,

Due to my inability to add, 5 more points were added to questions 3 and 4 of homework 6 to make the total 100. Sorry about this.

Richard,

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,

Office Hours

Hi class,

I'll be out of town for my office hours tomorrow (Monday). I'll be back Tuesday afternoon, in time for my regularly scheduled office hours on Wednesday. If you want to meet at some other time, feel free to send me an email, and I'll make sure to be available.

-- Aaron

I have several graded midterms. Let me know if you need them this weekend.

Gary Miller

Takehome Midterm and Assignment 4

Hi,

The take home midterm is available on the website and is due Monday before class. The scoring formula is mentioned once again on the first page.

Also, the due date of homework 4 is moved back to Wednesday.

Several people have asked about one complication resulting from question 2.1 on homework 4. The issue is about how to insert vertices in front of other vertices in the ordering and still be able to query whether one vertex comes before another in the ordering. There is a way to get around this issue by processing the entire graph again globally after building partial information. However, you can also use a data structure by Dietz and Sleator that supports both operations in O(1) worst case time. It can be found at http://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf if you are interested.

Richard,

Clarification on Hw4 Question 2.1

Several people have asked about whether "$v_i$ is connected to $v_j$, $v_k$" in the definition of deadend free ordering in question 2.1 means path connectivity. It should instead be "$v_i$ has edges to $v_j$, $v_k$". Also, note that there are no other assumptions on where $v_j$ and $v_k$ are in the ordering other than being before/after $v_i$.

Richard,