The first three will be oral presentation for ALL groups.
The fourth will be written presentation for ALL groups.

In fact, HBS next week WILL NOT FOCUS on this material, due to the
no-extension due date, and the HBS scheduled later in the week.  So - get
started right away!    Instead, HBS will help reinforce material on
randomized algorithms and/or other topics to be presented next week, for
which there will be no homework (but yes, exam-worthy).



1: [FOR ORAL PRESENTATION]  Chapter 11: Problem 1

2: [FOR ORAL PRESENTATION]
We'd like to send out holiday letters with high-resolution glossy images to
our relatives in Theoretica, where, due to lack of practical skills, the
residents have no digital capabilities, so we must rely on physical mail.

We know that there will be holiday parties hosted by Aunts A1, A2, ,,, Am,
and know which relatives (conveniently named 1, 2, ..., n) will be attending
which parties.  Our goal is to send a copy or our glossy packet to the fewest
number of Aunts to ensure that all of our relatives will have an opportunity
to see how well we're doing.

Unfortunately, the problem is NP-hard, and somebody suggests the following
greedy heuristic:  Pick the Aunt who will be hosting the largest party.
Then, pick the Aunt who will be hosting a party containing the most people
who were not at the first chosen Aunt's party.  Then, the Aunt whose guest
list contains the most of the remaining (apparently unpopular) guests....
etc.

We wonder how well this does.  In class we will see that there is a
guaranteed approximation, but here we will show just how badly it can do.
That is, you will argue that in the worst case, the ratio approximation it
achieves can be as bad as <blah>

To prove such things, rather than give a general argument showing that it
never does worst than <blah>, we construct a specific family of instances
I_n, parameterized by number of relatives n, for which this greedy approach
does particularly poorly.  Because this can be tricky, we do it for you, and
ask you to analyze the behavior of the greedy approach and make a conclusion
about its approximation-behavior.

Below is the guest-list of each of your Aunts, remembering that you have an
even number of relatives, named {1, 2, ..., n}

A1 = {1, 3, 5, 7, ..., n-1}   (what an odd party that will be)
A2 = {2, 4, 6, 8, ..., n}
A3 = {1, 2, 3, ..., 2n/3}
A4 = the first 2/3 of those not in A3)
A5 = the first 2/3 of those not in A3 or A4)
etc...
(as many more Aunts as you deem appropriate, following the same pattern.)



3. [FOR ORAL PRESENTATION] Chapter 11, problem 10


4. [FOR WRITTEN PRESENTATION] Chapter 11, problem 8