Homework 9: Big-Oh, Recurrence

Due 05.Apr.05 (Tue)

Before you tackle the homework, remind yourself of our general hw policies

Reading: Rosen §§ 2.2, 2.3 (skim), 6.1, 6.2, 6.3.

1. (4pts) In the definition of big-Oh, give particular values of c,n₀ (Rosen: "C,k") which witness:
   1. 17log(n)+19 is O(log n);
   2. n²log(n) is O(n³);
   3. n³+2 is O(n¹⁷).
2. (2pts) Section 2.2, #8 (p.142): Polynomial upper bounds.
3. (4pts) Section 2.2, #12 (p.142): x² vs x log(x).
4. (3pts) Section 2.2, #20a. (p.143): Simplify big-Oh.
   Recall your answer previous problems.
5. (2pts) Section 2.3, #12a,b. (p. 152): Some best-case performances.

6. (5pts) You have written a great new on-line multiplayer game, World of MathCraft, where many players will log in to your central server and play. Suppose that, for n players, your server needs to process f(n) network packets per second.

   1. How many players can you support simultaneously, if your server can handle 1000 packets per second?
   2. As expected, WoM is a wild success, and you are exceeding your original server capacity. You upgrade to a server farm which can handle 10 times as many packets per second (and probably costs you about 50 times as much; the cost of high-end performance tends to be super-linear). Now how many players can you support?
   Ian -- in future, use 10^5 and 10^8 or so. See sol'n set for the table-html. Use several columns, and *require* a program?
   1. f(n) = 2ⁿ
   2. f(n) = 1.1ⁿ (10% growth per new player)
   3. f(n) = n³
   4. f(n) = n²
   5. f(n) = n log(n)

7. (5pts extra-credit) (Adding big-Oh functions)
   1. (3pts) If f(n) is O(n²), show that g(n) = ∑_i=1ⁿ f(i) is O(n³).
      Hint: Start with the def'n of f being O(n²) to get some constants, and then work to find other constants which witness g being O(n³). You can keep your algebra fairly clear by using generously large constants.
   2. (2pts) Give a family of functions f_k(n), for k∈N, such that each f_k ∈ O(n²), yet g(n) = ∑_i=1ⁿ f_i(i) is not O(n³). Prove your answer.
      (To think about: Imagine trying to show this was impossible, by induction. Exactly where would the induction proof stall?)

8. (6pts) new problem, compensating for the deferral of the next two problems.
   Read Rosen's Closest-Pair problem at the end of § 6.3 in detail, and its very clever argument about why the ``conquer'' step of divide-and-conquer runs in linear time.

   Your friend Lÿnn Plaine has tried to improve on this algorithm by getting rid of the need to make a final pass looking for pairs of points which straddle the dividing line. Instead she'll make two overlapping sections, so that the closest pair is in one or the other. Given a set P of 2 or more points:

   • If |P| = 2, then she returns that pair and is done.

   • If |P| ≥ 3, she finds two coordinates x_a < x_b such than when she creates
     P_L = { (x,y) ∈ P | x < x_b}
     P_R = { (x,y) ∈ P | x_a < x}
     she gets |P_L| = |P_R| = (2/3)⋅|P|, as nearly as possible.
     Such a coordinate can be found quickly, if initially we sort the points by x-coordinate, as in Rosen.
     (We gloss over glitches about not being a multiple of three, and will also assume that no two points have the same x-coordinate.)

     She recursively computes the closest-pair in each of P_L and P_R, returns the closer of these two pairs.

   1. What is the recurrence relation describing her algorithm's running time, not counting the time to initially sort the points by x-coordinate?
   2. What is the closed form solution for this recurrence, by the Master Theorem? (Up to big-Oh.)
   3. If we go back and include the initial overhead of sorting the points by x-coordinate, what is the running time for the entire algorithm (up to big-Oh)?

   4. Searching for an improvement to her running time, you are brainstorming with her on ideas of how to shave the factor 2/3 down to any fraction strictly bigger than 1/2 — to 1/2+ε for any ε> 0, e.g. something like 51/100. In pushing the idea this far¹, the two of you start to get suspicious that this algorithm would really always work — couldn't the closest points happen to straddle that thin 2ε middle strip?

      Even in the algorithm as described (reducing the problem size by 2/3), give a set of points such that the closest-pair is actually one point from P_R-P_L, and one point from P_L-P_R (thereby spanning the entire middle section P_L∩ P_R).

9. (3pts) Section 6.2, #6 (p.423): dit,dah1,dah2
   Deferred until next week, after we've covered §6.2.
   After you set up a recurrence relation with initial conditions, I suggest you work out a few terms by hand before solving the recurrence, to get a feel for how the sequence grows.
10. (3pts) Section 6.2, #8 (p.423): average lobsters
    Deferred until next week, after we've covered §6.2.