Hints for Problem 2

Here are some hints for problem 2, for those of you who are stuck. Even though the solutions are all simple, for these problems its easy to think for awhile without getting anywhere. This should get you on the right track; feel free to email or visit office hours for further hints.

2a)
See if you can mentally divide the pizza into two sets in such a way that you can select every slice in one or the other of the sets, no matter what your opponent does. If you can do this, you are done, because one of the two sets has to have at least half of the pizza.

2b)
This problem doesn't depend on the specifics, like the exact size of the pepperonis. Think symmetry. Suppose we're playing on an annulus (a disk with a circle cut out of the middle). If I make the first move, what is some move you are guaranteed to be able to make? If you are the first player on a pizza, how can you guarantee that you will be the second player on an annulus?

For 2c:
It's a long standing open problem to actually come up with a winning strategy for the 1st player, so don't try to do that. Just prove one must exist. Suppose it were the case that the 2nd player had a winning strategy. What this means is that even if he were to tell you exactly what his strategy was, he could still win. Is this possible, or if he were to tell you his strategy in the chocolate bar game, could you use it to win yourself? An important property of this game is that many moves wipe out all sign of the previous history of the game in the current game state: for example, if I go first and select square (1,1), and you go second and select square (3,3), the state of the game is exactly the same as if you had gone first and selected square (3,3). The solution to this problem is a nice example of a nonconstructive proof.

Homework 1 Question 4

Thanks to several people who pointed this out during Aaron's office hours, what we thought was a minor detail on question 4 is a lot more complicated. The rearrangement of the 4 rank k subtrees causes changes to the parent pointers of their siblings, which are required to determine and fix violations. There exists a fairly complicated set of extra invariants on the violations that keeps this process at O(1) worst case, but that is beyond what is reasonable for this assignment. Sorry for this oversight.

As a result, your solutions may assume that there is an oracle which can support the rearrangement of rank-k subtrees and queries for parents in O(1) worst case time. You are also welcome to work towards the full solution for up to 20 bonus points.

HW0 solutions posted & HW1 modified

Hi,

Solutions to homework 0 have been posted on the course website. A typo in homework 1 question 4 has also been fixed.

Richard,

Office Hours Changed

Hi,

I've changed my office hours to Wednesday and Friday 3:00~4:30pm due to scheduling issues.

Richard,

Modified Office Hours

Hi class,

I will have to cancel my office hours this Monday (10:00 -- 11:00). Instead, I will have extended hours on Wednesday. In addition to my regular Wednesday office hours (also 10:00 -- 11:00), I'll be available to meet 12:30 -- 1:30.

Homework Zero Modified

The missing diagram was added to question 4 and part b) of it was removed. Question 5 was also modified to make it clear the domain of the function are the integers from 1 to n. Sorry about this.

Final Exam Reviews

Your final exam will be on Monday 05/04 from 1-4pm in WeH 7500. As usual, the exam is open-book, open-notes, etc. You should expect 6 - 8 questions, covering everything we have done in this class (but focusing on the materials after Midterm 2).

Here's the practice final we went over in class today (PDF). We ran out of time in the end, but there are a couple of things I wish I had time to talk about, so I'll just blog it here (hoping it will be useful when you study for the final).

A 2-approximation for the Steiner Tree Problem. Given a graph $G = (V, E)$ and a set of terminals $T \subseteq V$, we want to find a minimum-weight subgraph $S \subseteq G$ that connects all the terminals. This problem is known to be NP-hard, so we look for an approximation algorithm. Consider the following simple algorithm:

(1) construct a metric completion $G'$ of the graph $G$ on just the vertices of $T$,
(2) compute an MST $ST$ on $G'$,
(3) return $\widehat{S} = \cup_{e \in ST} \phi(e)$ (if you want your solution to be a tree, break cycles as necessary).

The metric completion $G'$ is basically a complete graph on $|T|$ nodes, where the weight on the edge between $u$ and $v$ is the distance of the shortest path between $u$ and $v$ in the original graph $G$. The function $\phi(u, v)$ returns the set of edges on the shortest path (in fact any shortest path) connecting $u$ and $v$.

Claim: $\widehat{S}$ is a feasible solution.

By construction, it is easy to see that $\widehat{S}$ (before we break any cycle) connects all the terminal pairs. Note that breaking cycles doesn't affect connectivity.

Claim: $\widehat{S}$ is a $2$-approximation.

Let $S^*$ be an optimal Steiner tree solution. Consider an Euler's tour $ET = \langle v_1, v_2, ..., v_{2|T|} \rangle$ on $S^*$ (with each edge doubled). Note that each original edge is traversed exactly twice, so $w(ET) = 2w(S^*)$. Create a new tour $ET'$ by dropping non-terminal vertices, and vertices that showed up earlier in the tour sequence. Thus $ET'$ contains distinct vertices, and $ET'$ is a spanning tree (we don't go back to where we started because that vertex already showed up in the tour). Furthermore, the weight of $ET'$, denoted by $w(ET')$, is at most $w(ET)$ by the triangle inequality. Since $ET'$ is a spanning tree, it cannot have a lower weight than the minimum spanning tree: $w(MST) \leq w(ET')$. Combining these little pieces together, we have $w(MST) \leq w(ET') \leq w(ET) = 2w(S^*)$. Finally, we observe that $w(\widehat{S}) \leq \sum_{e \in MST} w(\phi(e)) = w(MST)$, and hence $w(\widehat{S}) \leq 2w(S^*) = 2OPT$.