****************

1. In the text, problem 5.7.   Hint: Break the grid into quadrants, and look
at all "border" elements of each quadrant.


****************

2.  "Find the cookie".  I've hidden a cookie in one of n cookie jars.  For
only 1 cent, you can select a subset of the cookie jars, and I will tell you
whether or not the cookie is in one of the jars in your subset.   You can
repeat this as many times as you'd like (or you have pennies).

(a) How much will it cost you to find the cookie?  One approach, requiring n
cents in the worst case, is to simply ask for each jar separately whether or
not the cookie is in that jar.  Give a better solution, determine the worst
case cost, and prove that your method is optimal in the sense that any
strategy must cost at least as much in the worst case.  (We haven't
discussed lower bounds, but a simple "adversary" argument will suffice:
Argue that there is a way for me to answer questions "in the worst possible
way" for any strategy, and that I can force a worst case as bad as your
method achieves.)

(b) I am torn between wanting the cookie, and wanting money, and have a
momentary lapse of integrity.  Sometime during our interaction, I may fib,
and answer incorrectly.  Let's consider two strategies for you to find the
cookie, knowing that I may fib at most one time.

The "you can say that again" approach:
  Just rely on a strategy similar to the one in part (a), but ask redundant
questions to try to determine the lie, and compensate accordingly.

The "two will get you a quarter" approach:
   Using 2 questions, eliminate the largest fraction of possibilities that
you can, and recurse.

Fill in the exact details for the two strategies, how that they work, and
analyze the cost of a cookie in the worst case in each approach to determine
which is better.


*****************

3. Find the best mouthful of cookies..

A package of cookies bought at Chip's Exponentially Large Cookie Warehouse
contains n cookies (n a power of two), in a long box with all the cookies in
a single row.

Some cookies have chocolate chips, some have butterscotch chips, some have
both.  I love chocolate chips, and hate butterscotch.  My happiness on
eating a collection of cookies is exactly the number of chocolate chips
minus the number of butterscotch chips.     If I pick and choose cookies
from different places in the box, my brothers will accuse me of being
selfish.    I'd like to disguise my selfishness by finding a consecutive
sequence of cookies Ci, Ci+1, ... Ci+k, that I can eat that will maximize my
happiness.  This way, I can reply "huh?  I just grabbed a bunch together...
I wasn't trying to get just the best cookies".

(a) Show how I can find a consecutive sequence of cookies that maximizes my
happiness before my brothers get to the kitchen, which will happen in O(n^2)
time from now.

(b) Give a divide-and-conquer approach that will find the right consecutive
bunch to grab, even if my brothers are suspicious, and are rushing to get
here within O(n log n) time.

(c) Either in lecture, or in the next homework set, we'll probably see how
to select the best sequence of cookies in O(n) time.  Here however, we ask
the challenging question:  which is better, butterscotch or chocolate chip?